Python复杂性(运行时)

2024-03-28 10:23:43 发布

您现在位置:Python中文网/ 问答频道 /正文

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增长之间的关系的。有人能给我解释一下吗?


Tags: 函数列表lenreturn关系def线性f2
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()

。。。结果是

plot of function loops vs parameter size

水平轴是L的大小,垂直轴是函数循环的次数;从这里可以很明显地看到big-O。

好吧,既然这是家庭作业:

这是代码:

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约定所示)

基于Llen(),你多久循环一次?

(a)列表中项目的频率(b)列表中项目的频率?

(c)清单(d)中的项目比(b)中的项目出现的频率低?

我不是计算机科学专业的学生,我也不认为自己对这类理论有很强的理解力,但我认为从我的角度来看,有人试图给出一个答案可能是有意义的。

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

假设处理一个长度=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将关注这样一个事实,即i正在被乘法,以表示while循环需要多长时间和L的长度之间的关系。基本上,尝试比较while循环在len(L)的不同值下需要执行多少个循环,然后这将决定您的复杂性。1个时间单位可以是while循环中的1次迭代。

希望我在这里做出了一些贡献,因为我自己在这个问题上缺乏专业知识。

更新
为了根据ch3ka的注释进行澄清,如果您所做的工作超过了当前在with循环中所做的工作,那么您还必须考虑每个循环所增加的复杂性。但是因为你的list lookup ^{} is constant complexity和它后面的数学一样,我们可以忽略那些复杂性。

相关问题 更多 >