4T(n/2) + 42n的增长渐进阶
时间: 2023-06-10 13:07:17 浏览: 55
根据主定理(Master Theorem),可以得到递归式T(n) = 4T(n/2)的渐进阶为O(n^2)。具体的证明过程如下:
设T(n) = 4T(n/2),那么a = 4,b = 2,d = 0。
根据主定理的第一种情况,当a > b^d时,T(n)的渐进阶为O(n^logb(a))。因为4 > 2^0,所以满足第一种情况。
根据公式,logb(a) = log2(4) = 2,因此T(n)的渐进阶为O(n^2)。
因此,递归式T(n) = 4T(n/2)的渐进阶为O(n^2)。
相关问题
采用递归树求解以下递归方程;T(1)=1 T(n)=4T(n/2)+n 当n>时
我们先列出递归树:
第一层:T(n)
第二层:4T(n/2), 4T(n/2)
第三层:16T(n/4), 16T(n/4), 16T(n/4), 16T(n/4)
......
第i层:4^i T(n/2^i)个节点,每个节点的值为4^i T(n/2^i)
最后一层有T(1)个节点,单个节点的值为1。
根据递归方程的性质,当n>1时,T(n) = 4T(n/2) = 16T(n/4) = ... = 4^k T(n/2^k),其中2^k <= n < 2^(k+1)。
将T(n)最后一层到根节点路径上各节点的值累加起来,得到:
T(n) = 4^0 T(n/2^0) + 4^1 T(n/2^1) + 4^2 T(n/2^2) + ... + 4^k T(n/2^k)
= T(n/1) + 4T(n/2) + 4^2 T(n/4) + ... + 4^k T(n/2^k)
将式子中的k替换成log2 n,得到:
T(n) = T(n/1) + 4T(n/2) + 4^2 T(n/4) + ... + 4^(log2 n) T(n/2^log2 n)
化简一下:
T(n) = T(n/1) + 4T(n/2) + 4^2 T(n/4) + ... + 4^(log2 n) T(n/2^(log2 n))
= T(n/2) + 4T(n/2) + 4^2 T(n/2) + ... + 4^(log2 n - 1) T(n/2)
+ 4^(log2 n) T(1)
= (1 + 4 + 4^2 + ... + 4^(log2 n - 1)) T(n/2) + 4^(log2 n) T(1)
= (4^log2 n - 1)/(4 - 1) T(1) + 4^log2 n T(1)
= 3n - 2
因此,T(n) = 3n - 2。
T(n)=4T(n/2)+n^2 当n>1时
使用主方法(Master Theorem):
a = 4
b = 2
f(n) = n^2
logba = log24 = 2
因为f(n) = n^2 = Θ(n^(logb a)), 所以情形2适用,即
T(n) = Θ(n^(logb a) log n) = Θ(n^2 log n)
因此,当n>1时,T(n)的复杂度为Θ(n^2 log n)。