什么是+ 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

回答