蟒蛇發電機時間複雜性混亂

我一直在閱讀關於關鍵字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

謝謝你的回答。我想我清除了混亂。 –

蟒蛇發電機時間複雜性混亂

回答

相關問題