早教吧作业答案频道 -->数学-->
算法习题(1)用替换法证明T的渐近复杂性T（n）=T（n/2）+Θ（n）接近于Θ（nlogn）.（2）对于多项式f（n）=3n^3+2^n+3^n+6n^4+79,什么是紧约束（Θ）?并解释你的答案（简要地）.
题目详情
算法习题
(1)用替换法证明T的渐近复杂性T（n）=T（n/ 2）+Θ（n）接近于Θ（nlog n）.
（2）对于多项式f（n）=3n^3 + 2^n + 3^n + 6n^4 + 79,什么是紧约束（Θ）?并解释你的答案（简要地）.
(1)用替换法证明T的渐近复杂性T（n）=T（n/ 2）+Θ（n）接近于Θ（nlog n）.
（2）对于多项式f（n）=3n^3 + 2^n + 3^n + 6n^4 + 79,什么是紧约束（Θ）?并解释你的答案（简要地）.
▼优质解答
答案和解析
（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
对于任意整数n,存在k使得2^k
看了 算法习题(1)用替换法证明T...的网友还看了以下：
1/2*101/100=101/200这一步是因为什么这么做的?原题是1-1/2^2)(1-1/3 2020-05-14 …
观察下列等式：1^3=1^2,1^3+2^3=3^2,1^3+2^3+3^3=6^2,1^3+2^ 2020-05-15 …
帮我破解下这串数字什么意思9(2)4(3)6(2)2(1)4(3)3(1)4(3)9(1)6(3) 2020-05-17 …
天才进1,1,2,1,2,1,2,3,3,1,3,2,1,2,3,3,1,3,2,1,3,2,3, 2020-05-21 …
49.7-[-23/3/4+(18.7-25.25)]12+1又3/4-8又5/12-6.75-( 2020-06-04 …
观察下面的几个算式：1+2+1=41+2+3+2+1=91+2+3+4+3+2+1=161+2+3 2020-07-18 …
观察下面的几个算式：1+2+1=41+2+3+2+1=91+2+3+4+3+2+1=161+2+3 2020-07-18 …
1+2+2^2+2^3+2^4+``````+2^201+1/3+1/3^2+1/3^3+1/3^ 2020-07-18 …
已知:1^3=1=1^2,1^3+2^3=9=(1+2)^2,1^3+2^3+3^3=36=(1+ 2020-07-19 …
神奇的数列规律,你能想出来吗?1,2,1,2,3,2,1,2,3,4,3,2,1,2,3,4,5,4 2020-11-23 …