Python复杂性（运行时）

Question

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

设n为传递给此函数的列表的大小。以下哪项最准确地描述了这个函数的运行时是如何随着n的增长而增长的？

（a）它像n一样呈线性增长。 （b） 它呈二次生长，就像n^2一样。

（c）增长小于线性。 （d） 它的生长不止是二次的。

我不明白你是如何理解函数运行时和n增长之间的关系的。有人能给我解释一下吗？

Answer 1

以下是一个快速而肮脏的方法：

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的大小，垂直轴是函数循环的次数；从这里可以很明显地看到big-O。