1

クイックソート アルゴリズムの次の最悪のシナリオを証明しようとしていますが、問題が発生しています。最初に、n = ij のサイズ n の配列があります。アイデアは、Quicksort のすべての分割ステップで、1 つはサイズ i で、もう 1 つはサイズ i(j-1) の 2 つのサブ配列になるということです。この場合、i は 0 より大きい整数定数です。いくつかの例の再帰ツリーを引き出して、これが最悪のシナリオであり、実行時間が theta(n^2) になる理由を理解しました。これを証明するために、反復法を使用して再帰方程式を解きました。

T(n) = T(ij) = m if j = 1
T(n) = T(ij) = T(i) + T(i(j-1)) + cn if j > 1

T(i) = m
T(2i) = m + m + c*2i = 2m + 2ci
T(3i) = m + 2m + 2ci + 3ci = 3m + 5ci

したがって、再発は次のようになります。

                  j 
T(n) = jm + ci * sum k - 1 
                 k=1

この時点で、私は何をすべきかについて少し迷っています。最後の合計は、展開すると j^2 になるように見えますが、それが何らかの形で n^2 に等しいことを示す必要があります。これを続行する方法についての説明をいただければ幸いです。

4

2 に答える 2

1

クイックソート アルゴリズムの最悪のシナリオは、サイズ 0 と n-1 の 2 つのサブ問題がある場合です。このシナリオでは、各レベルに次の再帰方程式があります。

T(n)   = T(n-1) + T(0) < -- at first level of tree
T(n-1) = T(n-2) + T(0) < -- at second level of tree
T(n-2) = T(n-3) + T(0) < -- at third level of tree
.
.
.

各レベルのコストの合計は算術シリーズです。

        n       n(n-1)
T(n) = sum k =  ------ ~ n^2 (for n -> +inf)
       k=1        2

O(n^2)です。

于 2012-08-19T10:05:10.070 に答える
0

簡単な数学の問題です。あなたが正しく計算した複雑さは

O(jm + ij^2)

あなたが見つけたのは、パラメータ化された複雑さです。標準の O(n^2) は次のように含まれています。i=1 と仮定すると、標準の基本ケースがあるため、m=O(1) したがって j=n したがって、O(n^2) が得られます。ij=n を置くと、 O(nm/i+n^2/i) が得られます。ここで覚えておくべきことは、m は基本ケース アルゴリズムとして使用するものに応じた i の関数であるため、m=f(i) したがって、O(nf(i)/i + n^2/i が残ります。 ）。一般的なソートには線形アルゴリズムがないため、f(i) = omega(ilogi) で O(nlogi + n^2/i) が得られることに注意してください。したがって、自由度は i だけです。i の任意の値について、比較ベースの最適な境界である nlogn 未満に減らすことができないことを確認してください。

今私が混乱しているのは、クイックソートの最悪のケースの分析を行っているということです。これはその方法ではありません。最悪のケースを言うと、ランダム化を使用していることを意味します。この場合、最悪のケースは常に i=1 の場合であるため、最悪のケースの境界は O(n^2) になります。これを行うエレガントな方法は、R. Motwani と Raghavan によるランダム化されたアルゴリズムの本で説明されています。プログラマーの場合は、Cormen を参照してください。

于 2012-08-24T14:04:01.253 に答える