算法习题(1)用替换法证明T的渐近复杂性T（n）=T（n/2）+Θ（n）接近于Θ（nlogn）.（2）对于多项式f（n）=3n^3+2^n+3^n+6n^4+79,什么是紧约束（Θ）?并解释你的答案（简要地）.

Question

算法习题
(1)用替换法证明T的渐近复杂性T（n）=T（n/ 2）+Θ（n）接近于Θ（nlog n）.
（2）对于多项式f（n）=3n^3 + 2^n + 3^n + 6n^4 + 79,什么是紧约束（Θ）?并解释你的答案（简要地）.

Answer 1

（1）应该是2T(n/2)吧.先设 n=2^k,A(k)=T（2^k),则A(k)=2A(k-1)+Θ(2^k)=4A(k-2)+Θ(2^k+2^k)=...=2^k*A(0)+Θ(k*2^k) 得到T(n)=n+Θ(nlog n)=Θ(nlog n)
对于任意整数n,存在k使得2^k