什麼是+ N爲

對於這種算法，什麼是+ N爲

Bugs(n) 
    if n = 0 generate 5 bugs 
    else 
     Bugs(n-2); 
     for i ← 1 to n 
      generate 1 bug 
     Bugs(n-2);

遞推關係是：T(n) = 2T(n-2) + n, T(0) = 5

爲什麼會出現a +n？是因爲他們只有一個for循環，所以如果他們將兩個for循環會是+ n^2？

2011-04-27 Aaron

請不要置於「two for loops = n^2」，「one for loop = n」的謬論之下。這是迭代的次數，而不是嵌套循環的數量。 – 2011-04-27 15:13:02

但是不是迭代依賴於某種類型的循環嗎？ – Aaron 2011-04-27 15:21:23

我不清楚你的意思是「兩個循環」。如果它的意思是「兩個嵌套for循環，每次迭代從1到n」，那麼是的，它會是「+ n^2」。 – abeln 2011-04-27 15:25:14

遠遠看它做什麼了N = 0的情況：

總計：2T(n-2) + n

2011-04-27 15:09:26

謝謝，那麼你會改變「生成1個bug」爲n^2呢？ – Aaron 2011-04-27 15:19:52

@Aaron：好吧，「生成錯誤」會做到這一點...... – 2011-04-27 15:20:36

回答