如何用递归树求快速排序时间复杂度

      其实也就是点看算法导论的心得，感觉算法导论写的有点不详细的补充

快速排序 我的理解就是利用分治法 ，递归排序最后合并的排序，因为快速排序的最坏时间复杂度比较低所以快速被叫做快速排序如图

对于求快速排序的时间复杂度可以用递归树来做如图

递归式如下 

简化后对于快速排序用二分法如下

n代表规模如数组有16个数那么n就代表16 cn代表n次的分开数组，再合并数组所用的时间因为是一重循环所以用cn代替 .

下面我们用递归树求时间复杂度（还有很多方法这只是其中一种如图)

cn这个图比较难理解。下面来说一下意思

T（n）=2T（n/2)+cn 这里的常数是cn也就意味着递归到这里要加的数是cn 比如n为16的时候 cn 就是 16c 递归第一次就要2T（n/2)+16c  也就是说16c也就是cn是T(n)的一部分 那么可能有人要说了2T（n/2) 哪去了。。答案是2T（n/2)迭代递归了，递归的时候每次都加上一个常数 8c,4c,2c 递归到最后 也就是T(1)=c 而很明显这种递归这种常数就如 这树一样发展，从而形成了该递归树。而这递归树所有节点的和就是该递归式的时间复杂度

理解了这一层就好说了 因为每次都是二分和都是父节点所以每一层和总的节点和都是cn

然后求出树的深度就行了。比如就n=1那么就一层 n= 2 就2层 n=4就三层 。 很显然2的树的深度次方 减去 1就是 n的值  既 树的深度 k = log2n + 1 

既时间复杂度是每层的节点和 cn*k=cn*(log2n+1) = cnlog2n+n 忽略低阶项既 o(nlog2n)

简写为o(nlgn)

最后

以上就是彪壮黄蜂最近收集整理的关于如何用递归树求快速排序时间复杂度的全部内容，更多相关如何用递归树求快速排序时间复杂度内容请搜索靠谱客的其他文章。