假定有一个递归算法,其时间复杂度T(n)的递归定义为: T(n) ={8T(n/2) + O(nlogn),n> 1;1,n=1 求T(n)过程
时间: 2023-09-25 13:10:55 浏览: 124
根据递归定义,可以得到:
T(n) = 8T(n/2) + O(nlogn)
将n替换为n/2,得到:
T(n/2) = 8T(n/4) + O(nlog(n/2))
将T(n/2)代入T(n)中,得到:
T(n) = 8[8T(n/4) + O(nlog(n/2))] + O(nlogn)
化简,得到:
T(n) = 8^2 T(n/4) + 8O(nlog(n/2)) + O(nlogn)
以此类推,将T(n/4)代入T(n)中,得到:
T(n) = 8^3 T(n/8) + 8^2 O(nlog(n/4)) + 8O(nlog(n/2)) + O(nlogn)
化简,得到:
T(n) = 8^k T(n/2^k) + kO(nlog(n/2^k))
当n/2^k = 1时,即k=logn,代入上式可得:
T(n) = 8^logn T(1) + lognO(nlog1)
由于T(1)=1,8^logn = n^log8,O(nlog1) = O(1),代入上式可得:
T(n) = n^log8 + O(nlogn)
因此,该递归算法的时间复杂度为O(n^log8)。
阅读全文