python生成器时间复杂度混乱

发布时间：2020-12-20 11:56:49 所属栏目：Python 来源：网络整理

导读：我一直在阅读有关 python中关键字yield和生成器的内容,我想知道我是否理解它的时间复杂度. 这是我的生成器函数来获取因子： def calc_factors(n): for k in range(0,n+1): # this is the second "for" loop if n % k == 0: yield k 我会把这个生成器函数称为

我一直在阅读有关 python中关键字yield和生成器的内容,我想知道我是否理解它的时间复杂度.

这是我的生成器函数来获取因子：

def calc_factors(n):
    for k in range(0,n+1):     # this is the second "for" loop
        if n % k == 0:
           yield k

我会把这个生成器函数称为：

>>> for factor in calc_factor(100):   # this is the first "for" loop
        print factor

现在我的理解是,它具有O(n ^ 2)的时间复杂度,因为它有两个for循环,但我再次不相信.请在这方面赐教.
提前致谢！

解决方法

你误会了.你有一个O(n)循环.生成器函数上的循环不是嵌套循环,它只是在生成时从生成器接收每个项目.

换句话说,calc_factor(100)循环中的for因子直接与yield k表达式相关联;每次在calc_factor(100)循环中执行for因子时,前进一步.对于每个执行的yield k表达式,您将获得1个因子值. yield k执行(最多)n次,不再执行.

你可以在不过分夸大事实的情况下,将calc_factor(100)循环体中for因子中的所有代码想象为替换yield k行,其中factor = k.在您的情况下,您只使用打印因子,因此您可以使用打印k替换yield k而不会丢失功能.

如果您想以不同方式查看它,请取走生成器并构建列表.这就是您的代码在这种情况下所做的事情：

results = []
for k in range(0,n+1):
    if n % k == 0:
       results.append(k)

for factor in results:
    print factor

现在你还有两个循环,但它们不是嵌套的.一个是用于构建列表的O(n)循环,另一个是用于打印结果的O(k)循环(具有k ).这仍然是o(n)算法;常数乘数被忽略(你有o(2n)>

时间复杂度 - Gallop搜索时间复杂度？
时间复杂度 - 计算以下函数的时间复杂度
时间复杂度 - 各种序列类型的Common Lisp中ELT函数的时间复杂度
python - 函数的时间复杂度
时间复杂度 - 为什么冒??泡排序的时间复杂度最好的情况是O(n)
时间复杂度 - 迭代算法的时间复杂度
时间复杂度 - 这个递归Fibonacci的Big-O时间复杂度？
时间复杂度 - 理解时间复杂度：迭代算法

点击查看更多相关文章

转载注明原文：python生成器时间复杂度混乱 - 代码日志

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!