大 O 表示法 - python 函数

Question

这个函数的大 O 符号是什么（作为 n = len(lst) 的函数）：

def foo(lst):
    jump = 1
    total = 0
    while jump < len(lst):
        for i in range(0, len(lst), jump):
            total += i
        jump = jump * 2
    return total

我认为它是 O(n*log(n)) 但它不是，试图理解为什么它实际上是 O(n)... 我在这方面有点新，所以如果你也能解释你是如何得到答案的，那将是最好的！谢谢

Answer 1

函数复杂度为O(n)。

该函数进行了大约 2*n 次迭代以了解详细信息（但 2*n 在大 O 表示法中是 n）。

对于每个 while 循环，您将跳转到 2 的下一个幂，例如 n=1000:

[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]

然后对于每个子循环，您遍历所有元素，从而有效地执行 sum(successive_powers)（在示例中 1+2+4+…+512 = 1023）。

n次方的和大致就是n+1次方，所以这里：2**(log2(n)+1)~2*n.

一种简单的检查方法是更改代码：

def foo(lst):
    jump = 1
    total = 0
    while jump < len(lst):
        for i in range(0, len(lst), jump):
            total += 1 # count instead of summing
        jump = jump * 2
    return total

foo(list(range(1000)))
# 2000

Answer 2

您不断加倍步数：1, 2, 4, 8, ...

因此，您经过的那些范围 range(0, n, step) 的大小为 n、n/2、n/4、n/8、...（好吧，大约 - 四舍五入为整数).

它们的总和是 2n（大约）。这是 O(n).

如果您还不知道该总和，那么很容易看出：您从 0 开始。然后 n 使您达到 2n 的一半。添加 n/2 使您达到 1.5n，再次达到 2n 的一半。添加 n/4 使您达到 1.75，再次达到 2n 的一半。等等。你只会越来越接近2n。

大 O 表示法 - python 函数

Big O notation - python function

python

runtime

big-o

computer-science