算法~n=1时T(n)=O(1) ; n>1 时 T(n)=2*T(n/2)+O(n) ; 所以T(n) = O(nlgn)怎么做出来的?

来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 13:59:50
算法~n=1时T(n)=O(1);n>1时T(n)=2*T(n/2)+O(n);所以T(n)=O(nlgn)怎么做出来的?算法~n=1时T(n)=O(1);n>1时T(n)=2*T(n/2)+O(n)

算法~n=1时T(n)=O(1) ; n>1 时 T(n)=2*T(n/2)+O(n) ; 所以T(n) = O(nlgn)怎么做出来的?
算法~n=1时T(n)=O(1) ; n>1 时 T(n)=2*T(n/2)+O(n) ; 所以T(n) = O(nlgn)怎么做出来的?

算法~n=1时T(n)=O(1) ; n>1 时 T(n)=2*T(n/2)+O(n) ; 所以T(n) = O(nlgn)怎么做出来的?
为方便计算,假设 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)
所有对数的时间复杂度相等