5 
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 的增长之间的关系的。有人可以向我解释一下吗？

4

6 回答 6

12

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

这是代码：

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 约定所暗示的那样）

你多久循环一次，len()基于L？

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

(c) 较少，因为列表中的项目 (d) 比 (b) 更频繁？

于 2012-04-23T20:43:47.440 回答
10

我不是计算机科学专业的学生，​​我并不声称对这种理论有很强的掌握，但我认为从我的角度来看，尝试提供答案可能与某人相关。

你的函数总是需要时间来执行，如果它在一个可变长度的列表参数上运行，那么运行该函数所需的时间将与该列表中有多少元素有关。

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

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

如果它是 O(1) 复杂性（这实际上不是您的 AD 选项之一），那么这意味着无论 L 的大小如何，复杂性都不会增加。显然在您的示例中，它正在执行一个 while 循环，这取决于i在与 L 的长度的关系。我将关注i被相乘的事实，以表明通过该 while 循环所需的时间与 L 的长度之间的关系。基本上，尝试比较 while 循环的数量循环需要在 len(L) 的各种值下执行，然后这将决定您的复杂性。1 个时间单位可以通过 while 循环进行 1 次迭代。

希望我在这里做出了某种形式的贡献，因为我自己缺乏这方面的专业知识。

更新
根据 ch3ka 的评论进行澄清，如果你做的比你目前在with循环中所做的更多，那么你还必须考虑每个循环增加的复杂性。但是因为您的列表查找L[i]是恒定的复杂性，就像它后面的数学一样，我们可以忽略那些复杂性。

于 2012-04-23T19:57:55.190 回答
4

这是一种快速而肮脏的查找方法：

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 应该很明显。

于 2012-04-23T20:10:16.870 回答
3

考虑长度为 n=10 的输入会发生什么。现在考虑如果输入大小加倍到 20 会发生什么。运行时也会加倍吗？然后是线性的。如果运行时间增长了 4 倍，那么它是二次方的。等等。

于 2012-04-23T20:16:01.097 回答
2

查看函数时，您必须确定列表的大小将如何影响将发生的循环数。

在您的特定情况下，让我们增加 n 并查看 while 循环将运行多少次。

n = 0, loop = 0 times
n = 1, loop = 1 time
n = 2, loop = 1 time
n = 3, loop = 2 times
n = 4, loop = 2 times

看到图案了吗？现在回答你的问题，是吗：

(a) It grows linearly, like n does. (b) It grows quadratically, like n^2 does.

(c) It grows less than linearly. (d) It grows more than quadratically.

查看Hugh对经验结果的回答 :)

于 2012-04-23T20:13:16.997 回答
0

它是O(log(len(L)))，因为列表查找是一个恒定时间操作，与列表的大小无关。

于 2012-04-23T20:11:20.217 回答