algorithm - 求解递归函数的递归关系

Question

我需要为以下伪代码的最坏情况分析创建并求解递归关系。我正在计算添加的数字(不包括 for 循环计数器)作为我的基本操作。 我假设 n=2^k。

这是我取得的进步... 基本情况: T(n<=4) = 1

W(n)=W(2^k)=计算答案的加法+下一次递归的加法+for循环中的加法 W(2^k) = 2 + W(2^(k-2)) + (2^k) - 2 = W(2^(k-2)) + (2^k)

我使用反向替换并得到以下递推关系...

第j次递归调用 W(2^k) = W(2^(k-2j)) + (2^k) + sum(t=1,j,2^(k-2(t-1)))

我知道我可以简化它，因为我采用 W(2^(k-2j)) = W(4) 并求解 j 以查看代码需要多少递归步骤。 在这种情况下，j=(k/2) - 1。减少重复给了我...

W(2^k) = 1 + (2^k) + sum(t=1,j,2^(k-2(t-1))).

减少总和使我...

W(2^k) = 1 + (2^k) + (2^k)*(2^2)*sum(t=1,j,2^(-2t)) 或

W(n) = 1 + n + 4n*sum(t=1,j,2^(-2t))

我无法简化的是求和。在讲座中，我们可能会有 sum(i=1,n,2^i) 的求和，即 2^(n+1)-1，但这次不同。

int function calc(int n) {
   int num,answer;
   if(n<=4) {return n+10;}
   else {
     num=calc(n/4);
     answer=(num+num+10);
     for(int i=2;i<=n-1;i++) {
         answer=answer+answer;
     }
     return answer;
  }
}

如有任何帮助，我们将不胜感激。这个任务今晚到期。谢谢

Answer 1

问题的时间复杂度是T(n) = T(n/4) + n。术语 n 可能表示 \Theta(n)。因此，T(n) = n + n/4 + n/4^2 + ... + n/(4^log_4(n)) = n(1 + 1/4 + ... + 1/n) =\Theta(n)。请注意 lim_{n\to\infty} 1 + 1/4 + ... + 1/4^log_4(n) = 4/3 这是一个常数。