python generators时间复杂度混乱 [英] python generators time complexity confusion

问题描述

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

I have been reading about keyword yield and generators in python and I want to know if I have understood it right it terms of time complexity.

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

Here is my generator function to get factors:

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

，我将此生成器函数称为：

and I would call this generator function as:

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

<现在我的理解是，它具有O（n ^ 2）的时间复杂度，因为它有两个for循环，但是我仍然不相信。请在这方面启发我。
预先感谢！

Now my understanding is that this has time complexity of O(n^2) as it has two for loops but again I'm not convinced. Please enlighten me on this front. Thanks in advance!

推荐答案

您误会了。您有一个O（n）循环。生成器函数上的循环不是嵌套循环，它只是从生成器中接收生成的每一项。

You misunderstood. You have a O(n) loop. The loop over the generator function is not a nested loop, it merely receives each item from the generator as it is yielded.

，则直接连接到calc_factor（100）循环中的收益k 表达;每次在calc_factor（100）循环中执行 for factor时，都会前进一个步骤。对于每个执行的 yield k 表达式，您将获得1个 factor 值。 收益k 执行（最多） n 次，不再执行。

In other words, the for factor in calc_factor(100) loop is directly connected to the yield k expression; each time that executes the for factor in calc_factor(100) loop advances one step. You get 1 factor value for every yield k expression executed. yield k executes (up to) n times, no more.

您可以在不过度强调事实的情况下，将calc_factor（100）循环主体中 for因数的所有代码想象为替换 yield k 行，其中 factor = k 。在您的情况下，您仅使用 print factor ，因此可以将 yield k 替换为 print k 而不会损失任何功能。

You can, without bending the truth too much, imagine all code in the for factor in calc_factor(100) loop body as replacing the yield k line, with factor = k. In your case you only use print factor, so you could replace the yield k with print k with no loss of functionality.

如果您想换个角度看，请拿走发电机并建立一个清单。在这种情况下，这就是您的代码要做的事情：

If you want to look at it differently, take away the generator and build a list. This is what your code does in that case:

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））。

Now you have two loops still, but they are not nested. One is a O(n) loop to build the list, the other is a O(k) loop (with k < n) to print the results. This would still be a O(n) algorithm; constant multipliers are ignored (you'd have O(2n) -> O(n)).

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

All the generator does is remove the intermediary list. You don't have to first collect all the results, you get to have access to each result immediately.

这篇关于python generators时间复杂度混乱的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！