0

CLRS は、i が p と r の間の確率変数である場合に交換A[r]するように指示します。A[i]ただし、クイックソート関数のピボットとして変数をランダムに選択し、値を交換した場合、時間の複雑さはどうなりますか?

アルゴリズムのパフォーマンスは、本に記載されているものよりも悪くなりますか?

ここにコードがあります 

 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)- それはまだ起こりえますが、低い確率です。
アイデアは、悪意のある入力の攻撃に対するアルゴリズムの回復力を高めることです。

ピボットが疑似ランダムに選択されている場合、どの配列が最悪のケースの動作を引き起こすかを予測するのははるかに困難です。 .

もう 1 つの問題は、データが特定のパターンで表示される傾向がある場合、最悪のケースが何度も (高い確率で) 繰り返されないようにすることです。

補足として、「従来の」クイックソートのように最初 (または最後) の要素をピボットとして使用することは、実際のアプリケーションで配列がソートされるか、ほぼソートされる可能性が予想よりもはるかに高いため、悪い考えです。アルゴリズムが最悪のケースの動作にかなり頻繁に陥る原因となります。詳細については、このスレッドを参照してください:既にソートされているファイルをソートするのにかかる時間に関心があるのはなぜですか?

于 2015-06-25T16:54:22.323 に答える
0

特定のアルゴリズムの Big-O の複雑さについて話すとき。多くの場合、理論的な平均時間の複雑さについて話しています。ただし、時間の複雑さが平均よりもはるかに悪いという最悪のシナリオがあることに注意する必要があります。

たとえば、クイック ソート O(n log n) の平均的な計算の複雑さ。ただし、元の配列が完全に逆になり、不適切なピボットを選択した場合、最悪のケースは O(n2) です。

于 2015-06-25T17:39:36.503 に答える