快速排序的算法复杂度？

Question

我发现了以下快速排序算法:

function quicksort(array)
    less, equal, greater := three empty arrays
    if length(array) > 1  
        pivot := select any element of array
        for each x in array
            if x < pivot then add x to less
            if x = pivot then add x to equal
            if x > pivot then add x to greater
        quicksort(less)
        quicksort(greater)
        array := concatenate(less, equal, greater)

我想通过找递归关系来分析它的算法。对于我每次调用此算法时所看到的，例如，通过选择主元，在原始数组的第一个位置。它使用生成的两个列表再次调用快速排序，所以我将:

                   one list ------ pow(2,0)=1
                less       greater--------2 lists----pow(2,1)=2
   less greater              less greater-------4 lists---pow(2,2)=4

所以它似乎形成了一种二叉树，所以如果我得到模式，它将是:2^k=n，其中 k 是递归的级别，所以我将有 O(log n)

但是如何对重复分析做同样的事情呢？我的意思是，因为我没有计算函数的去栈过程，所有递归算法都会发生这种情况。

有什么帮助吗？谢谢

Answer 1

首先，您应该考虑快速排序不是确定性的。所以你应该对最坏情况-最好情况-平均情况进行分析。

以最坏情况为例:

T(n) = T(n-1) + O(n)

O(n) 来自于您正在对整个数组进行分区这一事实。T(n-1) 相反是在最坏情况下要划分的元素数。

如果你使用主定理解决递归问题，你将得到 O(n^2)

同样在最好的情况下:

T(n) = 2T(n/2) + O(n)

这与合并排序相同，再次应用主定理得到 O(nlogn)。