T(n)=4T(n/2)+n^2/lgn 求时间复杂度

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/11/06 06:50:19

T(n)=4T(n/2)+n^2/lgn 求时间复杂度
主方法不适用 ,用递归树做

因为O(log2(N))=O(lg(N))=O(ln(N)) 所以不区分 log2(n),lg(n),ln(n);
T(n)=4T(n/2)+n^2/lgn
T(n/2)=4T(n/4)+(n/2)^2/lg(n/2)
T(2) =4T(1) +4log2(2) ;
S(T(n)) -T(1)=S(T(n/2))+ S(n^2 log2(n))
T(n) -T(1) =S(i^2log2(i)) ;=2^m
不妨设 i=2^m
T(n) -T(1) =S(i^2log(i)) =S((2^m)^2 *m)
S(i^2)
再问：答案好像是 n^2lg(lgn)
再答： 1)抱歉计算错了，n^2/lgn看成n^2 lgn 了。 2）答案是对的，下面给出精确计算。 3） T(n)= O(N^2LOG^2(N)) //=O((nlogn)^2) T(n)=4T(n/2)+n^2/lgn 不妨设n=2^m ;Tm(m-i) = T(n/2^i-1) T(n)=Tm(m) = 4Tm(m-1) +n^2/lg(n) =4^(m-1)*T(1)+∑（4^(m-i)* (2^i)^2/i ） // i= 2~ m =(n/2)^2*T(1) + ∑（ (2^m)^2 /i ） =(n/2)^2*T(1) + ∑(1/i) * n^2 // i= 2~ m 因为： ∑(1/i) = 1/2 +1/3+1/4+1/5+1/6+1/7+1/8+..... >= 1/2 +1/4+1/4 + 1/8+1/8+1/8+1/8 = log(i)/2=O(log(log(N))) ∑(1/i) = 1/2 +1/3+1/4+1/5+1/6+1/7+1/8+.....

T(n)=4T(n/2)+n^2/lgn 求时间复杂度 T（n）=n!/((n-k)!) 求时间复杂度O() 若一个算法中的语句频度之和为T(n)=n+2nlogn,则算法的时间复杂度为? 代换法解递归式证明T(n)=T(n/2)+1的解为O(lgn) 若一个算法中的语句频度之和为T(n)=6n+3nlogn+n*n,则算法的时间复杂度为? lgM+lgN=2lg(M-2N)求log根号2（M/N)的值 2lg[1/2(m-n)]=lgm+lgn,求m/n的值若2lg(M-2N)=lgM+lgN,求M/N的值已知2lg[1/2(m-n)]=lgm+lgn,求m/n的值?/ 若一个算法中的语句频度之和为T（n）=1024n+4nlogn,则算法的时间复杂度为0（nlogn m^(lgn)=n^(lgm) 求整数n(n>=0)阶乘的算法如下,其时间复杂度: