Quicksort奇怪的时间复杂度,c ++
voi*_*ois 12 c++ algorithm performance quicksort time-complexity
我一直在测试不同数字序列的不同排序算法的时间复杂度,直到我得到快速排序(在中间有枢轴)的结果一直是一半上升而另一半下降的序列.图:
("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);
}
}
有没有人知道是什么导致了这种奇怪的结果？
TL; DR:问题是枢轴选择策略,这使得在这些类型的输入(A形和V形序列)上反复做出差的选择.这导致快速排序产生高度"不平衡"的递归调用,这反过来导致算法执行得非常差(A形序列的二次时间).
恭喜,您已经(重新)发现了选择中间元素作为枢轴的快速排序版本的对抗性输入(或者更确切地说是一系列输入).
作为参考,A形序列的一个例子是1 2 3 4 3 2 1,即增加的序列,到达中间的选择,然后减少; V形序列的一个例子是4 3 2 1 2 3 4,即减少的序列,在中间达到最小值,然后增加.
想想当你选择中间元素作为A形或V形序列的枢轴时会发生什么.在第一种情况下,当你传递算法的A形序列时1 2 ... n-1 n n-1 ... 2 1,枢轴是数组中最大的元素 - 这是因为A形序列的最大元素是中间的,你选择中间element作为pivot ---你将对大小的子数组进行递归调用0(你的代码实际上不会对0元素进行调用)和n-1.在下一次调用大小n-1的子数组时,您将选择子数组的最大元素(它是原始数组的第二大元素)的枢轴; 等等.这会导致性能不佳,因为运行时间为O(n)+ O(n-1)+ ... + O(1)= O(n ^ 2),因为在每个步骤中,您基本上都会传递几乎整个数组(除了pivot之外的所有元素,换句话说,递归调用中数组的大小是高度不平衡的.
这是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形序列的运行时间实际上是 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)时间内以高概率运行.(但是,请注意,要显示这个尖锐的尾部边界,您需要对输入进行一些假设;如果数字都是不同的,结果肯定会成立;例如,请参阅Motwani和Raghavan的随机算法手册.)
为了证实我的说法,如果你随机选择一个支点,这里是相同序列的运行时间图表x = tab[l + (rand() % (p-l))];(确保你srand(time(NULL))在主要部分打电话).对于A形序列:
对于V形序列:
对于数据集中的 n 个条目，快速排序的最坏情况时间复杂度为 O(n^2)，平均时间复杂度为 O(n log n)。有关时间复杂度分析的更多详细信息，请参见此处：
https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort
和这里：
http://www.cise.ufl.edu/class/cot3100fa07/quicksort_analysis.pdf