请问快速排序的时间复杂度是怎么推算的？

来源：百度知道 编辑：UC知道 时间：2024/05/19 01:52:20
说快速排序的时间复杂度最好为O(nlgn),即：每次都可以分为均匀两段，根据这个，如何推算出时间复杂度为O(nlgn)？？？？？？？？？？？？？？？？

每次分成两段，那么分的次数就是logn了哦，每一次处理需要n次计算，那么时间复杂度就是nlogn了！
注意这是平均时间复杂度，因为你分的时候可能并不均匀！
根据平均情况来说是O(nlogn),因为在数据分布等概率的情况下对于单个数据来说在logn次移动后就会被放到正确的位置上了。
最坏是O(n^2).这种情况就是数组刚好的倒序，然后每次去中间元的时候都是取最大或者最小。