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

clz80012022-10-04 11:39:541条回答

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

已提交,审核后显示!提交回复

共1条回复
小鸟大鸟 共回答了21个问题 | 采纳率100%
因为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)
1年前

相关推荐