求解递归函数的递归关系
Solving a recurrence relation for a recursive function
我需要为以下伪代码的最坏情况分析创建并求解递归关系。我正在计算添加的数字(不包括 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;
}
}
如有任何帮助,我们将不胜感激。这个任务今晚到期。谢谢
问题的时间复杂度是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
这是一个常数。
- T(n) = T(2^k) // 根据假设
- T(n) = T(n/4) + n // 是递归关系
- T(2^k) = T(2^(k-2)) + (2^k) // 重写
- T(2^k) = T(2^(k-2j)) + (2^k)*SUM(i=0;j-1;(1/4)^i) // 是迭代 j
的关系
- T(4) = T(2^(k-2j)) = 1 // 递归结束时,到达base case,只加1次
- 2^2 = 2^(k-2j) // 重写并删除 T
- 2=k-2j // 去掉公共碱基
- j=(k/2)-1 // 求解第 j 次迭代
- 注意:迭代不能有小数,所以j=CEILING((k/2)-1)
- SUM(i=0;j-1;(1/4)^i) = (1-(1/4)^j)/(1-(1/4))
- 上面的几何和和变换证明,见下面的 wiki link
- 将j代入CEILING((k/2)-1),求和为...
- 总和 = (1-(1/4)^(上限((k/2)-1)))/(1-(1/4))
- 最后,T(2^k) = 1 + (2^k)*SUM
- 根据输入n,T(n) = 1 + (n*SUM)
- 这个公式适用于所有 k>=1
正在测试几个值...
- k=1, T(2) = 1 + (2*0) = 1 // 我们知道这是真的因为 T(2) 是一个基本情况
- k=2, T(4) = 1 + (4*0) = 1 // 我们知道这是真的因为 T(4) 是一个基本情况
- k=3, T(8) = 1 + (8*1) = 9 // 通过递推公式,T(8) = T(2) + 8 = 9, true
- k=4, T(16) = 1 + (16*1) = 17 // 通过递推公式,T(16) = T(4) + 16 = 17, true
- k=5, T(32) = 1 + (32*1.25) = 41 // 通过递推公式,T(32) = T(8) + 32, T(8) = 9, 32+ 9=41 真
这是我取得的进步... 基本情况: 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;
}
}
如有任何帮助,我们将不胜感激。这个任务今晚到期。谢谢
问题的时间复杂度是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
这是一个常数。
- T(n) = T(2^k) // 根据假设
- T(n) = T(n/4) + n // 是递归关系
- T(2^k) = T(2^(k-2)) + (2^k) // 重写
- T(2^k) = T(2^(k-2j)) + (2^k)*SUM(i=0;j-1;(1/4)^i) // 是迭代 j 的关系
- T(4) = T(2^(k-2j)) = 1 // 递归结束时,到达base case,只加1次
- 2^2 = 2^(k-2j) // 重写并删除 T
- 2=k-2j // 去掉公共碱基
- j=(k/2)-1 // 求解第 j 次迭代
- 注意:迭代不能有小数,所以j=CEILING((k/2)-1)
- SUM(i=0;j-1;(1/4)^i) = (1-(1/4)^j)/(1-(1/4))
- 上面的几何和和变换证明,见下面的 wiki link
- 将j代入CEILING((k/2)-1),求和为...
- 总和 = (1-(1/4)^(上限((k/2)-1)))/(1-(1/4))
- 最后,T(2^k) = 1 + (2^k)*SUM
- 根据输入n,T(n) = 1 + (n*SUM)
- 这个公式适用于所有 k>=1
正在测试几个值...
- k=1, T(2) = 1 + (2*0) = 1 // 我们知道这是真的因为 T(2) 是一个基本情况
- k=2, T(4) = 1 + (4*0) = 1 // 我们知道这是真的因为 T(4) 是一个基本情况
- k=3, T(8) = 1 + (8*1) = 9 // 通过递推公式,T(8) = T(2) + 8 = 9, true
- k=4, T(16) = 1 + (16*1) = 17 // 通过递推公式,T(16) = T(4) + 16 = 17, true
- k=5, T(32) = 1 + (32*1.25) = 41 // 通过递推公式,T(32) = T(8) + 32, T(8) = 9, 32+ 9=41 真