22

クイックソートと、それを再帰的方法と反復的方法の両方で実装する方法について学びました。
反復法の場合：

  1. 範囲（0 ... n）をスタックにプッシュします
  2. 指定された配列をピボットで分割します
  3. 一番上の要素をポップします。
  4. 範囲に複数の要素がある場合は、パーティション（インデックス範囲）をスタックにプッシュします
  5. スタックが空になるまで、上記の3つの手順を実行します

そして、再帰バージョンはwikiで定義されている通常のバージョンです。

再帰的アルゴリズムは、反復的アルゴリズムよりも常に遅いことを学びました。
それで、時間計算量の観点からどちらの方法が好ましいですか（メモリは問題ではありません）？
プログラミングコンテストで使用するのに十分速いのはどれですか？
c ++ STL sort（）は再帰的アプローチを使用していますか？

4

3 に答える 3

25

（漸近的な）時間計算量に関しては、どちらも同じです。

「再帰は反復よりも遅い」-このステートメントの背後にある理論的根拠は、再帰スタックのオーバーヘッド（呼び出し間の環境の保存と復元）によるものです。
ただし、これらは一定の操作数ですが、「反復」の数は変更されません。

再帰的および反復的なクイックソートはどちらも、O(nlogn) 平均的なケースとO(n^2) 最悪のケースです。

編集：

楽しみのために、投稿に（java）コードを添付してベンチマークを実行し、次にwilcoxon統計テストを実行して、実行時間が実際に異なる確率を確認しました。

結果は決定的なものになる可能性があります（P_VALUE = 2.6e-34、https： //en.wikipedia.org/wiki/P-value。P_VALUEはP（T> = t | H）であることに注意してください。ここで、Tはテスト統計であり、 Hは帰無仮説です）。しかし、答えはあなたが期待したものではありません。
反復解の平均は408.86ミリ秒でしたが、再帰解の平均は236.81ミリ秒でした。

（注-私は引数としてIntegerではなく使用しました-そうでなければ、再帰ははるかに良く達成されたでしょう、なぜならそれは多くの整数をボックス化する必要がないので、これも時間がかかります-反復解は選択の余地がないので私はそれをしましたがそうする。intrecursiveQsort()

したがって、-あなたの仮定は真実ではありません。再帰的な解決策は、P_VALUE = 2.6e-34の反復的な解決策よりも高速です（私のマシンとJavaの場合は少なくとも）。

public static void recursiveQsort(int[] arr,Integer start, Integer end) { 
    if (end - start < 2) return; //stop clause
    int p = start + ((end-start)/2);
    p = partition(arr,p,start,end);
    recursiveQsort(arr, start, p);
    recursiveQsort(arr, p+1, end);

}

public static void iterativeQsort(int[] arr) { 
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(0);
    stack.push(arr.length);
    while (!stack.isEmpty()) {
        int end = stack.pop();
        int start = stack.pop();
        if (end - start < 2) continue;
        int p = start + ((end-start)/2);
        p = partition(arr,p,start,end);

        stack.push(p+1);
        stack.push(end);

        stack.push(start);
        stack.push(p);

    }
}

private static int partition(int[] arr, int p, int start, int end) {
    int l = start;
    int h = end - 2;
    int piv = arr[p];
    swap(arr,p,end-1);

    while (l < h) {
        if (arr[l] < piv) {
            l++;
        } else if (arr[h] >= piv) { 
            h--;
        } else { 
            swap(arr,l,h);
        }
    }
    int idx = h;
    if (arr[h] < piv) idx++;
    swap(arr,end-1,idx);
    return idx;
}
private static void swap(int[] arr, int i, int j) { 
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public static void main(String... args) throws Exception {
    Random r = new Random(1);
    int SIZE = 1000000;
    int N = 100;
    int[] arr = new int[SIZE];
    int[] millisRecursive = new int[N];
    int[] millisIterative = new int[N];
    for (int t = 0; t < N; t++) { 
        for (int i = 0; i < SIZE; i++) { 
            arr[i] = r.nextInt(SIZE);
        }
        int[] tempArr = Arrays.copyOf(arr, arr.length);
        
        long start = System.currentTimeMillis();
        iterativeQsort(tempArr);
        millisIterative[t] = (int)(System.currentTimeMillis()-start);
        
        tempArr = Arrays.copyOf(arr, arr.length);
        
        start = System.currentTimeMillis();
        recursvieQsort(tempArr,0,arr.length);
        millisRecursive[t] = (int)(System.currentTimeMillis()-start);
    }
    int sum = 0;
    for (int x : millisRecursive) {
        System.out.println(x);
        sum += x;
    }
    System.out.println("end of recursive. AVG = " + ((double)sum)/millisRecursive.length);
    sum = 0;
    for (int x : millisIterative) {
        System.out.println(x);
        sum += x;
    }
    System.out.println("end of iterative. AVG = " + ((double)sum)/millisIterative.length);
}
于 2012-09-23T14:48:56.657 に答える
9

再帰は必ずしも反復より遅いとは限りません。クイックソートはその完璧な例です。これを繰り返し行う唯一の方法は、スタック構造を作成することです。したがって、他の方法では、再帰を使用する場合にコンパイラーが行うのと同じことを行います。おそらく、これはコンパイラーよりも悪い結果になります。また、再帰を使用しない場合（値をポップしてスタックにプッシュするため）、ジャンプが増えます。

于 2012-09-23T14:47:38.883 に答える