0

CLRS 告诉我们交换A[r]其中A[i]i 是 p 和 r 之间的随机变量。但是，如果我要随机选择一个变量作为快速排序函数中的枢轴并交换值，那么现在的时间复杂度是多少？

该算法现在的性能会比书中给出的更差吗？

这是代码 

 package Clrs;
    import java.util.Random;
    public class Clrs
    {
        public static void main(String[] args) 
        {
                int[] a = new int[]{7,6,5,4,3,2,1}; 
                quicksort(a,0,a.length-1);
                        System.out.println(); 

            for (int i : a) {
            System.out.println(i);
            }
    }
    static void  quicksort(int a[],int p,int r)
    {
     int q;
     if(p<r)
     {
            Random random = new Random();
            int y = p+random.nextInt(r-p+1);
            int temp = a[y];
            a[y]=a[r];
            a[r]=temp;
            q = partition(a,p,r);
            quicksort(a,p,q-1);
            quicksort(a,q+1,r);
     }
    }
    static int partition(int a[],int p,int r)
    {        
        int x=a[r];
        int i=p-1;
        for (int j = p; j <= r-1; j++) {
            if(a[j]<=x)
            {
                i++;
                swap(a,i,j);
            }                       
        }        
        swap(a,i+1,r);      
        return i+1;
    }
    static void swap(int a[],int x,int y)
    {
        int t=a[x];
        a[x]=a[y];
        a[y]=t;
    }
}
4

2 回答 2

3

理论复杂度保持不变。O(nlogn)平均情况和O(n^2)最坏情况。

选择随机枢轴的想法不是消除最坏情况下的性能O(n^2)- 这仍然可能以低概率发生。
这个想法是使算法对恶意输入的攻击更具弹性。

当枢轴被伪随机选择时，很难预测哪个数组会导致最坏情况的行为，所以如果有人想攻击我们的程序，并导致它的工作速度明显变慢 - 他会更难做到这一点.

另一个问题是确保如果您的数据倾向于以某种模式出现 - 最坏的情况不会一遍又一遍地重复（很有可能）。

作为旁注，将第一个（或最后一个）元素作为“经典”快速排序所做的枢轴是一个坏主意，因为在现实生活中的应用程序中，数组被排序或几乎排序的概率远高于人们的预期，导致算法经常陷入最坏情况的行为。关于它的更多信息可以在这个线程中找到：为什么我们对排序一个已经排序的文件需要多长时间感兴趣？

于 2015-06-25T16:54:22.323 回答
0

当我们谈论某些算法的 Big-O 复杂度时。我们经常谈论理论平均时间复杂度。尽管您必须意识到，在最坏的情况下，时间复杂度可能比平均水平要差得多。

例如，快速排序 O(n log n) 平均计算复杂度。但最坏的情况是 O(n2) 当您的原始数组完全反转并且您选择了错误的枢轴时。

于 2015-06-25T17:39:36.503 回答