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

好的，既然这是家庭作业：

代码如下：

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

循环执行了多少次？ 这显然取决于L的大小。 让我们称之为loops(L)

所以我们得到了

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

作为一个好人，我要告诉你，列表查找在python中是不变的，所以它可以归结为

O(loops(L))（常量因子被忽略，正如big-O约定所暗示的那样）

根据L的len()循环的频率是多少

（a）列表中有项目的频率（b）列表中有项目的频率为二次

（c）由于清单（d）中的项目比（b）中的项目更频繁，因此次数较少

Answer 2

我不是计算机科学专业的学生，我也不认为自己对这类理论有很强的掌握，但我认为，从我的角度来看，有人可能会尝试给出一个答案

您的函数总是需要时间来执行，如果它在不同长度的列表参数上运行，那么运行该函数所需的时间将与该列表中的元素数量有关

让我们假设处理长度==1的列表需要1个单位的时间。问题是，列表的大小变大与此函数执行时间的增加之间的关系

这个链接分解了一些大O表示法的基础：http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

如果它是O（1）复杂度（这实际上不是你的A-D选项之一），那么它意味着复杂度永远不会增长，而不管L的大小。显然，在你的例子中，它在做一个while循环，依赖于相对于L的长度增长一个计数器。i。我将关注i正在被乘以的事实，为了说明完成while循环所需的时间与L的长度之间的关系。基本上，试着比较while循环在len（L）的不同值下需要执行多少个循环，然后这将确定您的复杂性。通过while循环，1个时间单位可以是1次迭代

希望我在这里做出了一些贡献，因为我自己在这方面缺乏专业知识

更新
基于CH3KA的注释，如果你做的比你目前在^ {CD3}}循环中所做的要多，那么你还必须考虑每个循环的复杂度。但是因为你的list lookup ^{} is constant complexity，跟它后面的数学一样，我们可以忽略那些复杂性方面的问题

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的大小，纵轴是函数循环的多少倍；从这个角度来看，big-O应该是非常明显的