这是我的生成器函数来获取因子:
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循环,但我再次不相信.请在这方面赐教.
提前致谢!
换句话说,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
相关文章
时间复杂度 - Gallop搜索时间复杂度? 时间复杂度 - 计算以下函数的时间复杂度 时间复杂度 - 各种序列类型的Common Lisp中ELT函数的时间复杂度 python - 函数的时间复杂度 时间复杂度 - 为什么冒泡排序的时间复杂度最好的情况是O(n) 时间复杂度 - 迭代算法的时间复杂度 时间复杂度 - 这个递归Fibonacci的Big-O时间复杂度? 时间复杂度 - 理解时间复杂度:迭代算法 点击查看更多相关文章转载注明原文:python生成器时间复杂度混乱 - 代码日志
总结以上是内存溢出为你收集整理的python生成器时间复杂度混乱全部内容,希望文章能够帮你解决python生成器时间复杂度混乱所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)