c++ - 快速排序奇怪的时间复杂度，C++

Question

我一直在测试不同数字序列的不同排序算法的时间复杂度，并且一切顺利，直到我得到了一半升序和另一个降序序列的快速排序(中间有枢轴)结果。图表:



(“V”表示前半部分下降，另一半部分上升的序列，“A”表示前半部分上升，另一半部分下降的序列。)

其他类型序列的结果看起来和我预期的一样，但也许我的算法有问题？

void quicksort(int l,int p,int *tab)
{
int i=l,j=p,x=tab[(l+p)/2],w; //x - pivot
do 
{
    while (tab[i]<x)
    {
        i++;
    }
    while (x<tab[j])
    {
        j--;
    }
    if (i<=j)
    {
        w=tab[i];
        tab[i]=tab[j];
        tab[j]=w;
        i++;
        j--;
    }
}
while (i<=j);
if (l<j)
{
    quicksort(l,j,tab);
}
if (i<p)
{
    quicksort(i,p,tab);
}
}

有没有人知道是什么导致了如此奇怪的结果？

Answer 1

TL;DR:问题在于枢轴选择策略，它在这些类型的输入(A 形和 V 形序列)上反复做出糟糕的选择。这些导致快速排序进行高度“不平衡”的递归调用，进而导致算法性能非常差(A 形序列的二次时间)。

恭喜，您已经(重新)发现了选择中间元素作为枢轴的快速排序版本的对抗性输入(或者更确切地说是一系列输入)。

作为引用，A 形序列的示例是 1 2 3 4 3 2 1 ，即增加的序列，到达中间的pick，然后减少； V 形序列的一个例子是 4 3 2 1 2 3 4 ，即一个序列减少，在中间达到最小值，然后增加。

想想当您选择中间元素作为 A 形或 V 形序列的支点时会发生什么。在第一种情况下，当您通过算法时，A 形序列 1 2 ... n-1 n n-1 ... 2 1 ,pivot是数组中最大的元素---这是因为A型序列的最大元素是中间的，你选择中间的元素作为pivot---并且你会对子数组进行递归调用尺寸0 (您的代码实际上并未调用 0 元素)和 n-1 .在下一次调用大小为 n-1 的子数组中您将选择子数组的最大元素(原始数组的第二大元素)作为主元；等等。这会导致性能不佳，因为运行时间是 O(n)+O(n-1)+...+O(1) = O(n^2) 因为在每一步中你基本上都传递了几乎整个数组(除主元之外的所有元素)，换句话说，递归调用中数组的大小高度不平衡。

这是 A 形序列的轨迹 1 2 3 4 5 4 3 2 1 :

blazs@blazs:/tmp$ ./test 
pivot=5
   1   2   3   4   1   4   3   2   5
pivot=4
   1   2   3   2   1   3   4   4
pivot=3
   1   2   3   2   1   3
pivot=3
   1   2   1   2   3
pivot=2
   1   2   1   2
pivot=2
   1   1   2
pivot=1
   1   1
pivot=4
   4   4
   1   1   2   2   3   3   4   4   5

您可以从跟踪中看到，在递归调用时，算法选择一个最大的元素(最多可以有两个最大的元素，因此文章 a，而不是 the)作为主元。这意味着 A 形序列的运行时间实际上是 O(n)+O(n-1)+...+O(1) = O(n^2)。 (在技术术语中，A 形序列是对抗性输入的一个例子，它迫使算法表现不佳。)

这意味着，如果你为“完美”的 A 形序列绘制运行时间

1 2 3 ... n-1 n n-1 ... 3 2 1

为增加 n ，你会看到一个很好的二次函数。这是我刚刚为 n=5,105, 205, 305,...,9905 计算的图表对于 A 形序列 1 2 ... n-1 n n-1 ... 2 1 :



在第二种情况下，当你向算法传递一个 V 形序列时，你选择数组的最小元素作为主元，因此将对大小为 n-1 的子数组进行递归调用。和 0 (您的代码实际上并未调用 0 元素)。在下一次调用大小为 n-1 的子数组中您将选择最大的元素作为枢轴；等等。 (但您不会总是做出如此糟糕的选择；关于这种情况，很难说更多。)由于类似的原因，这会导致性能不佳。这种情况稍微复杂一些(这取决于您如何进行“移动”步骤)。

这是 V 形序列的运行时间图 n n-1 ... 2 1 2 ... n-1 n为 n=5,105,205,...,49905 .运行时间不太规律——正如我所说，它更复杂，因为您并不总是选择最小的元素作为枢轴。图表:



我用来测量时间的代码:

double seconds(size_t n) {
    int *tab = (int *)malloc(sizeof(int) * (2*n - 1));
    size_t i;

    // construct A-shaped sequence 1 2 3 ... n-1 n n-1 ... 3 2 1
    for (i = 0; i < n-1; i++) {
        tab[i] = tab[2*n-i-2] = i+1;
        // To generate V-shaped sequence, use tab[i]=tab[2*n-i-2]=n-i+1;
    }
    tab[n-1] = n;
    // For V-shaped sequence use tab[n-1] = 1;

    clock_t start = clock();
    quicksort(0, 2*n-2, tab);
    clock_t finish = clock();

    free(tab);

    return (double) (finish - start) / CLOCKS_PER_SEC;
}

我修改了您的代码以打印算法的“跟踪”，以便您可以自己玩弄它并深入了解正在发生的事情:

#include <stdio.h>

void print(int *a, size_t l, size_t r);
void quicksort(int l,int p,int *tab);

int main() {
    int tab[] = {1,2,3,4,5,4,3,2,1};
    size_t sz = sizeof(tab) / sizeof(int);

    quicksort(0, sz-1, tab);
    print(tab, 0, sz-1);

    return 0;
}


void print(int *a, size_t l, size_t r) {
    size_t i;
    for (i = l; i <= r; ++i) {
        printf("%4d", a[i]);
    }
    printf("\n");
}

void quicksort(int l,int p,int *tab)
{
int i=l,j=p,x=tab[(l+p)/2],w; //x - pivot
printf("pivot=%d\n", x);
do 
{
    while (tab[i]<x)
    {
        i++;
    }
    while (x<tab[j])
    {
        j--;
    }
    if (i<=j)
    {
        w=tab[i];
        tab[i]=tab[j];
        tab[j]=w;
        i++;
        j--;
    }
}
while (i<=j);

print(tab, l, p);
if (l<j)
{
    quicksort(l,j,tab);
}
if (i<p)
{
    quicksort(i,p,tab);
}
}

顺便说一句，我认为如果您对每个输入序列取 100 次运行时间的平均值，则显示运行时间的图表会更平滑。

我们看到这里的问题是枢轴选择策略。让我注意，您可以通过随机化枢轴选择步骤来缓解对抗性输入的问题。最简单的方法是随机统一选取枢轴(每个元素同样有可能被选为枢轴)；然后你可以证明算法在 O(n log n) 时间内运行 with high probability . (但是，请注意，要显示这种尖尾边界，您需要对输入进行一些假设；如果数字都是不同的，则结果肯定成立；例如，参见 Motwani 和 Raghavan 的《随机算法》一书。)

为了证实我的说法，如果您随机均匀地选择枢轴，这里是相同序列的运行时间图， x = tab[l + (rand() % (p-l))]; (确保您在主目录中调用 srand(time(NULL)))。
对于 A 形序列:


对于 V 形序列: