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。
好吧,既然这是家庭作业:
这是代码:
这显然取决于len(L)。
所以让我们看看每一行的成本是多少:
这些显然是恒定的时间,独立于L。 在循环中,我们有:
循环执行了多少次? 这显然取决于L的大小。 我们称之为
loops(L)
所以我们得到了
loops(L) * (timelookup(L) + const)
作为一个好人,我会告诉你列表查找在python中是不变的,所以它可以归结为
O(loops(L))
(忽略常量因子,如big-O约定所示)基于
L
的len()
,你多久循环一次?(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次迭代。希望我在这里做出了一些贡献,因为我自己在这个问题上缺乏专业知识。
更新} is constant complexity 和它后面的数学一样,我们可以忽略那些复杂性。
为了根据ch3ka的注释进行澄清,如果您所做的工作超过了当前在
with
循环中所做的工作,那么您还必须考虑每个循环所增加的复杂性。但是因为你的list lookup ^{相关问题 更多 >
编程相关推荐