快排的最好和最坏时间复杂度

快排是选取某个值,让数组左边部分都小于这个值,右边部分都大于这个值。然后再递归处理左右两边。

当每次分区的时候,左右两边的数组个数刚好相等或者接近相等的话,则能获得最好的时间复杂度。这里假设两边的个数相等,则可以得到下面的递推公式。

T(1) = C;   n=1 时,只需要常量级的执行时间,所以表示为 C。
T(n) = 2*T(n/2) + n; n>1

这个公式推导到最后,可以得到最好的时间复杂度为 O(nlogn)。然后来看下最坏的时间复杂度,根据上面可以知道,最坏的情况也就是每次分区左右两边最不平衡的时候。比如下面这个排序好的数组

[1, 3, 5, 6, 8]

根据这个快排实现,大概可以经历下面的过程

[1, 3, 5, 6, 8]
[3, 5, 6, 8]
[5, 6, 8]
[6, 8]

可以看到总共需要 4 轮分区的操作,这个实现用的分区算法,每次都需要从右到左扫描一遍元素。

while (l[j] > pivotValue && j > left) {
    j--;
}

多举几个例子就会发现,数组中有多少个元素,就需要多少轮分区,每次分区大概需要扫描 n/2 个元素。所以总的时间复杂度就为

O(n * n/2) => O(n^2)

(完)

2018.12.03
Powered by Cubi,  Hosted by Coding Pages