不太理解快速排序算法的时间复杂度
来源：3-6 随机化快速排序法
松柏i
2019-07-22
(即每个结点都把当前数组分成两个大小相等的数组结点,n个元素数组的根结点的分解次数就构成一棵完全二叉树)。这时分解次数等于完全二叉树的深度log2n;每次快速排序过程无论把数组怎样划分、全部的比较次数都接近于n-1次，所以最好情况下快速排序算法的时间复杂度为O(nlog2n):
这是我在网上找到分析时间复杂度的资料，我的疑问是，为什么分解的次数等于完全二叉树的深度呢？如果这样类比，二分搜索并不需要将每个结点都走一遍，而快速排序要经过每个节点呀？我的理解有错误吗？
写回答
1回答
-
1
为什么分解的次数等于二叉树的深度？
n个元素，一分为2;
每n/2个元素，再一分为2；
每n/4个元素，再一分为2；
...
最后分到只剩下一个元素。
一共多少层？log2(n)这么多层。就是二叉树的深度。
当然了，由于快排每次分割点不确定，是随机的，所以真正计算快排的时间复杂度，计算的是期望值。这已经远远超出这个课程的内容了。在算法导论中，讲解快排的时候，有快排复杂度证明的严格推导，感兴趣可以参考。
也可以参考这里：https://coding.imooc.com/learn/questiondetail/15858.html
2
二分搜索并不需要将每个结点都走一遍？
是的。二分搜索的过程，根据当前要搜索的元素和中间元素的大小，选择继续在左边或者右边的一边，进行搜索就好了；
但是快排，排完左边，还要排右边，两边都需要兼顾：）
继续加油！：）
012019-07-23
相似问题
请问一路的快排的时空复杂度怎么计算呢？
回答 1
老师我不明白希尔排序为什么能那么快
回答 1