Python复杂度（运行时）

Python复杂度（运行时）

好的，因为这是家庭作业：

这是代码：

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

它显然取决于len（L）。

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

sum = 0i = 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

循环执行了多少次？它显然取决于L的大小。

loops(L)

所以我们的整体复杂度为

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

作为我的好人，我会告诉您列表查找在python中是恒定的，因此归结为

O(loops(L))

（如big-O约定所暗示的，常量因子被忽略）

而你多久循环的基础上

len()

的

L

？

（a）列表中的项目的频率（b）列表中的项目的频率两倍？

（c）减少频率，因为（d）列表中的项目比（b）频率更高？