Python的复杂性（运行时）(Python complexity (run-time))

def f2(L):
    sum = 0
    i = 1
    while i < len(L):
        sum = sum + L[i]
        i = i * 2
    return sum

设n是传递给这个函数列表L的大小。以下哪项最准确地描述了此功能的运行时如何成长为N变？

（一）它呈线性增长，如N一样。（B）它平方增长，像N ^ 2一样。

（C）它生长小于线性。（d）它的生长比二次方更多。

我不明白你怎么找出功能的运行时间和n的增长之间的关系。有人可以解释这样对我？

Answer 1:

没关系，因为这是家庭作业：

这是代码：

def f2(L):
    sum = 0
    i = 1
    while i < len(L):
        sum = sum + L[i]
        i = i * 2
    return sum

这显然是依赖于LEN（L）。

因此，让我们看到的每一行，它的成本：

sum = 0
i = 1
# [...]
return sum

这些显然是恒定的时候，L的独立的在我们的循环：

    sum = sum + L[i] # time to lookup L[i] (`timelookup(L)`) plus time to add to the sum (obviously constant time)
    i = i * 2 # obviously constant time

而循环中执行了多少次？这是obvously依赖于L的大小允许调用loops(L)

所以我们得到的总体复杂性

loops(L) * (timelookup(L) + const)

身为好人的我，我会告诉你该列表查找是在Python恒定的，所以把它归结为

O(loops(L))忽略常数因子，如大O约定暗示）

而你多久循环的基础上， len()的L ？

（一）经常因为有在名单（二）项目二次尽可能经常有列表中的项目？

（c）中不经常因为有在列表中（d）项往往比（B）？

Answer 2:

我不是计算机专业的，我不要求有这种理论的强抓，但我想这可能是相关的人从我的角度，试图促成一个答案。

你的函数总是需要时间来执行，如果它是在不同长度的list参数运行，那么所花费的时间来运行该功能会相对多少元素在该列表中。

让我们假设它需要的时间为1个单元，处理长度== 1，什么问题是问的名单，在名单挺大VS增加时间，这个函数执行的大小之间的关系。

此链接打破了大O符号的一些基础知识： http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

如果是O（1）复杂性（这是不是真正的你的AD选项之一），那么这将意味着无论是复杂永不L的大小上生长柜台显然在你的例子是做一个while循环依赖i相对于L的长度我将专注于一个事实，即i被相乘，以表明它之间要花多长时间通过while循环VS L的长度得到基本上，尝试了多少环比的关系while循环将需要在LEN（L）的不同值执行，然后将决定你的复杂性。 1个单位的时间可以是1次迭代通过while循环。

希望我已经取得了一些形式在这里的贡献，就这个问题我自己的专业知识的缺乏。

更新
为了阐明基于从ch3ka的评论，如果你做的比你现在有你的里面更多的with循环，那么你就还必须考虑每个循环增加了复杂性。但是因为你的列表查找L[i]是恒定的复杂性，因为是它后面的数学，我们可以忽略那些在复杂性方面。

Answer 3:

这里有一个快速和肮脏的方式来了解一下：

import matplotlib.pyplot as plt

def f2(L):
    sum = 0
    i = 1
    times = 0
    while i < len(L):
        sum = sum + L[i]
        i = i * 2
        times += 1    # track how many times the loop gets called
    return times

def main():
    i = range(1200)
    f_i = [f2([1]*n) for n in i]
    plt.plot(i, f_i)

if __name__=="__main__":
    main()

...这会导致

横轴为L的大小，纵轴是功能多少次循环; 大O应该从这个很明显的。

Answer 4:

考虑长度为n = 10的输入会发生什么。现在考虑会发生什么，如果输入大小加倍到20请问运行双呢？然后，它是线性的。如果运行时通过生长因子4，那么它的平方。等等。

Answer 5:

当你在看功能，您必须确定如何列表的大小会影响到将要发生的循环数。

在您的具体情况，让增量n和看到while循环多少次运行。

n = 0, loop = 0 times
n = 1, loop = 1 time
n = 2, loop = 1 time
n = 3, loop = 2 times
n = 4, loop = 2 times

看到这个模式？现在回答你的问题，做的：

(a) It grows linearly, like n does. (b) It grows quadratically, like n^2 does.

(c) It grows less than linearly. (d) It grows more than quadratically.

结帐休的答案的实证结果:)