algorithm - 3 方向クイックソートの Big-O Bound の証明

Question

3 ウェイ クイックソート (デュアル ピボット クイックソート) の場合、Big-O バウンドを見つけるにはどうすればよいですか? 誰かがそれを導出する方法を教えてもらえますか?

Answer 1

アルゴリズムの複雑さを見つけることとそれを証明することの間には微妙な違いがあります。

このアルゴリズムの複雑さを見つけるには、他の回答でamitが言ったように行うことができます。平均nして、サイズの問題を3つの小さなサイズの問題に分割するn/3ので、èlog_3（n）`になります。平均して、サイズ1の問題へのステップ。経験を積むと、このアプローチの感覚をつかみ始め、関連するサブ問題の観点からアルゴリズムを考えるだけで、アルゴリズムの複雑さを推測できるようになります。

このアルゴリズムが平均的なケースで実行されることを証明するには、マスター定理を使用します。これを使用するには、配列の並べ替えに費やした時間を与える再帰式を作成する必要があります。前述したように、サイズの配列の並べ替えは、サイズの3つの配列の並べ替えと、それらの作成に費やした時間に分解できます。これは次のように書くことができます：O(nlogn)nn/3

T(n) = 3T(n/3) + f(n)

ここT(n)で、は、サイズの入力n（実際には必要な基本演算の数）の解決に「時間」をf(n)与え、問題をサブ問題に分割するために必要な「時間」を与える関数です。

3方向クイックソートのf(n) = c*n場合、配列を確認するため、各アイテムを配置する場所を確認し、最終的にスワップを行います。これにより、マスター定理のケース2f(n) = O(n^(log_b(a)) log^k(n))になります。これは、一部k >= 0の場合（この場合k = 0）は次のように述べています。

T(n) = O(n^(log_b(a)) log^(k+1)(n)))

a = 3とb = 3（漸化式からこれらを取得します）としてT(n) = aT(n/b)、これは次のように単純化されます。

T(n) = O(n log n)

そしてそれは証拠です。

Answer 2

まあ、同じ証明が実際に成り立ちます。

各反復は、配列を 3 つのサブリストに分割します。平均して、これらのサブリストのサイズはn/3それぞれ です。
したがって、必要な反復回数は、1回に達するまでlog_3(n)の回数を見つける必要があるためです(((n/3) /3) /3) ...。これにより、次の式が得られます。

n/(3^i) = 1

これは に対して満足されi = log_3(n)ます。

各反復は引き続きすべての入力を処理します (ただし、別のサブリスト内にあります) - クイックソートと同じで、O(n*log_3(n)).

からlog_3(n) = log(n)/log(3) = log(n) * CONSTANT、実行時間はO(nlogn)平均的であることがわかります。

サブリストのサイズを計算するためにより悲観的なアプローチをとった場合でも、一様分布の最小値を取ることによって、サイズ 1/4 の最初のサブリスト、サイズ 1/2 の 2 番目のサブリスト、および の最後のサブリストを取得することに注意してください。サイズ 1/4 (一様分布の最小値と最大値)、これは再びlog_k(n)反復に減衰します (異なる k>2 を使用) - これはO(nlogn)全体的に得られます - 再び。

---

形式的には、証明は次のようになります:
各反復は、いくつかの定数 c_1,N_1 に対してc_1* n、各 に対して実行するのに最大でも op しかかかりません。n>N_1(ビッグ O 表記の定義、および各反復がO(n)再帰を排除しているという主張。これが真である理由を自分自身で納得させてください。ここで注意してください - 「反復」とは、特定の「レベル」でアルゴリズムによって行われるすべての反復を意味し、特定の「レベル」ではありません。単一の再帰呼び出し)。

上記のように、log_3(n) = log(n)/log(3) 平均的なケースで反復があります（ここでは楽観的なバージョンを使用します。悲観的な場合と同じ原則を使用できます）

T(n)これで、アルゴリズムの実行時間は次のようになります。

for each n > N_1:
T(n) <= c_1 * n * log(n)/log(3) 
T(n) <= c_1 * nlogn

ビッグオー表記の定義でT(n)は、との中にあることを意味O(nlogn)します。 QEDM = c_1N = N_1