蟒蛇发电机时间复杂性混乱

我一直在阅读关于关键字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），因为它有两个循环，但我不相信。请在这方面给我启发。在此先感谢！

来源

2016-12-30 d-coder

你不能只计算你的程序中的循环，并坚持计数旁边的n ^。时间复杂性不会那样工作。 – user2357112

虽然在语法上，您有两个循环，生成器中的循环只有一个迭代执行循环的生成器外的每个迭代。花费的时间总量与n成正比，而不是n^2。 – user2357112

@ user2357112：感谢您的评论。我很困惑，因为它看起来像第一个for循环执行，然后它会调用生成器函数，但然后生成器函数有另一个for循环让我这么想。我同意计算'for'循环是不正确的方法来判断时间复杂度。 –

你误会了。你有一个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，所以你可以用print 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 < n）来打印结果。这仍然是一个O（n）算法;常数乘数被忽略（你会有O（2n） - > O（n））。

所有发电机都是删除中间名单。您不必首先收集所有结果，即可立即访问每个结果。

来源

2016-12-30 18:17:56

所以'calc_factor（n）'里面的'for'循环不被考虑？ –

@ d-coder：当然是。但是，循环*生成器结果不是一个新的循环。每次你进入下一个结果（这会使它成为n ** 2），你不会在calc_factor（）中运行循环的* all *，你会遍历生成器的所有结果。 –

非常感谢您的回答。你的回答清除了我的困惑。 –

不，这应该只有时间复杂度O（n）。

在真正的嵌套循环，每迭代外循环引起全一套内部循环的迭代：

for i in range(100):  # 100 times 
    for j in range(i): # i times, for *each* of the 100 values of i 
     # do something

但在发电机，yield声明的原因和立即从发电机返回控制权。所以每次发生器迭代时只计数为，其中一个通过发生器的循环。

所以你的for factor in calc_factor(100):调用发生器每发生器的循环一次。所以从某种意义上说，这个是发生器的循环;它只是从发电机外部进行控制。因此，不是外部嵌套循环。

来源

2016-12-30 18:22:01

谢谢你的回答。我想我清除了混乱。 –

蟒蛇发电机时间复杂性混乱

回答

相关问题