python生成器时间复杂度混乱

Question

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

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

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循环,但我再次不相信.请在这方面赐教.提前致谢!

Answer 1

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

换句话说,for factor in calc_factor(100)循环直接连接到yield k表达式; 每次执行for factor in calc_factor(100)循环都会前进一步.factor每个yield k执行的表达式都会获得1个值.yield k执行(最多)n次,不再执行.

你可以,但不可弯曲真相太多,想象中的所有代码for factor in calc_factor(100)循环体作为替代的yield k路线,用factor = k.在您的情况下,您只使用print factor,因此您可以替换yield k使用print 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 <n).这仍然是O(n)算法; 常数乘数被忽略(你有O(2n) - > O(n)).

所有生成器都会删除中间列表.您不必先收集所有结果,您可以立即访问每个结果.