T(n)=4T(n/2)+n^2/lgn 求时间复杂度
答案:1 悬赏:0 手机版
解决时间 2021-01-24 02:56
- 提问者网友：原来太熟悉了会陌生
- 2021-01-23 05:41
主方法不适用 ，用递归树做
最佳答案
- 五星知识达人网友：十年萤火照君眠
- 2021-01-23 05:59
^因为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) <T(n)-T(1) <lg(n)S(i^2)
S (i^2)=2^(m+1)-1=(N+1)^2+1 =O(N^2)
lg(n)S(i^2)=O(N^2log(N))
所以
T(N)=O(N^2log(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) <T(n)-T(1) <lg(n)S(i^2)
S (i^2)=2^(m+1)-1=(N+1)^2+1 =O(N^2)
lg(n)S(i^2)=O(N^2log(N))
所以
T(N)=O(N^2log(N))
数学没学好，哎，似乎不能更精确了！
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯