Python复杂性(运行时)

Question

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

设n是传递给该函数的列表L的大小.以下哪项最准确地描述了此函数的运行时如何随着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)) (常数因素被忽略,正如大O惯例所暗示的那样)

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

(a)列表(b)中的项目是否经常与列表中的项目一样频繁？

(c)由于(d)项中的项目多于(b)项,因此较少见？

Answer 2

我不是计算机科学专业,我并不认为对这种理论有很强的把握,但我认为从我的角度来看,尝试提供答案的人可能是相关的.

您的函数总是需要时间来执行,如果它在不同长度的列表参数上运行,那么运行该函数所花费的时间将取决于该列表中的元素数量.

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

此链接打破了Big O表示法的一些基础知识:http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

如果它是O(1)复杂度(实际上并不是你的AD选项之一),那么无论L的大小如何,它都意味着复杂性永远不会增长.显然,在你的例子中,它依赖于i在与L的长度的关系.我将重点关注i正在乘以的事实,以指示通过该循环所需的时间与L的长度之间的关系.基本上,尝试比较多少循环循环将需要在len(L)的各种值下执行,然后这将决定您的复杂性.1个单位的时间可以通过while循环进行1次迭代.

希望我在这里做出了某种形式的贡献,我自己在这个问题上缺乏专业知识.

更新
要根据ch3ka的注释进行说明,如果你在with循环中所做的工作比你现有的更多,那么你还必须考虑每个循环增加的复杂性.但是因为你的列表查找L[i]是恒定的复杂性,就像它后面的数学一样,我们可以忽略那些复杂性.