python生成器时间复杂度混淆

Question

我一直在阅读有关关键字 yield 和 python 中的生成器的信息，我想知道我是否正确理解了它的时间复杂度。

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

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) 循环时前进一步。每执行一个 yield k 表达式，您都会得到 1 个 factor 值。 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))。

生成器所做的只是删除中间列表。您不必先收集所有结果，您可以立即访问每个结果。