算法~n=1时T(n)=O(1) ; n>1 时 T(n)=2*T(n/2)+O(n) ; 所以T(n) = O(nlg

算法~n=1时T(n)=O(1) ; n>1 时 T(n)=2*T(n/2)+O(n) ; 所以T(n) = O(nlgn)怎么做出来的?
nilainizou2003 1年前 已收到1个回答 举报
赞

whd8818 幼苗

共回答了20个问题采纳率：95% 举报

为方便计算,假设 n = 2^k,因此：
T(n) = 2T(n / 2) + O(n)
= (4T(n / 4) + 2O(n/2)) + O(n)
= ((8T(n / 8) + 4O(n/4)) + O(n)) + O(n)
=…
= 2^kT(1) + O(n) + … + O(n) + O(n) + O(n)
= nO(1) + k * O(n) = (k + 1)O(n) = O(n * log2n)
所有对数的时间复杂度相等

1年前 追问

9

nilainizou2003 举报

不大理解2^kT(1)是怎么来的 能回答下吗？？谢谢~~~
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.034 s. - webmaster@yulucn.com