アルゴリズムイントロダクション輪講 B4 田中翔

範囲 7章 ヒープソート と 8章 クイックソート

7章 ヒープソート 実行時間は𝑂(𝑛 log 𝑛) その場での(in place)ソーティング よりよい特性を兼ね備えている。 7章　ヒープソート 実行時間は𝑂(𝑛 log 𝑛) マージソートと同様で挿入ソートと異なる その場での(in place)ソーティング 挿入ソートと同様でマージソートと異なる よりよい特性を兼ね備えている。 “ヒープ”と呼ぶデータ構造を使用 ヒープソートに有効なだけでなく、プライオリティキューを効率良く実現する。

7章 ヒープ 完全ができる配列のオブジェクト ↑配列で表現されたヒープ ↑二分木で表現されたヒープ 16 14 10 7章　ヒープ 完全ができる配列のオブジェクト 1 16 2 3 1 2 3 4 5 6 7 8 9 10 14 10 16 14 10 8 7 9 3 2 4 1 4 5 6 7 8 7 9 3 8 9 10 2 4 1 ↑配列で表現されたヒープ ↑二分木で表現されたヒープ

7章 ヒープ ヒープを表す配列は𝑙𝑒𝑛𝑔𝑡ℎ[𝐴]とheap-size[𝐴]の2つの属性を持つオブジェクト 𝑙𝑒𝑛𝑔𝑡ℎ[𝐴]:配列の要素数 7章　ヒープ ヒープを表す配列は𝑙𝑒𝑛𝑔𝑡ℎ[𝐴]とheap-size[𝐴]の2つの属性を持つオブジェクト 𝑙𝑒𝑛𝑔𝑡ℎ[𝐴]:配列の要素数 heap-size[𝐴]:配列𝐴に格納されているヒープの要素数 PARENT(𝑖) return 𝑖/2 LEFT(𝑖) return 2𝑖 RIGHT(𝑖) return 2𝑖 + 1 ヒープ条件 𝐴[PARENT(𝑖)] ≧ 𝐴[𝑖]

7章 ヒープ 5つの基本的な手続き HEAPIFY BUILD-HEAP HEAPSORT EXTRACT-MAXとINSERT 7章　ヒープ 5つの基本的な手続き HEAPIFY ヒープ条件を保持するために主要な役割を果たし、𝑂( lg 𝑛) 時間で動作 BUILD-HEAP 順序がついていない入力の配列からヒープを構成し、線形時間で動作 HEAPSORT 配列をその場でソートし、𝑂(𝑛 lg 𝑛) 時間で動作 EXTRACT-MAXとINSERT ヒープのデータ構造をプライオリティキューとして用いるときに使用し、𝑂( lg 𝑛) 時間で動作

7章 ヒープの条件の保持 HEAPIFY(𝐴, 𝑖) 1 𝑙 ← LEFT(𝑖) 2 𝑟 ← RIGHT(𝑖) 7章　ヒープの条件の保持 HEAPIFY(𝐴, 𝑖) 1 𝑙 ← LEFT(𝑖) 2 𝑟 ← RIGHT(𝑖) 3 if 𝑙≤ heap-size[𝐴] かつ 𝐴[𝑙] > 𝐴[𝑖] then 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 ← 𝑙 else 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 ← 𝑖 6 if 𝑟≤ heap-size[𝐴] かつ 𝐴[𝑟] > 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡] 7 then 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 ← 𝑟 8 if 𝑙𝑎𝑟𝑔𝑒𝑠𝑡≠𝑖 9 then 値の交換 𝐴[𝑖] ↔ 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡] 10 HEAPIFY(𝐴, 𝑙𝑎𝑟𝑔𝑒𝑠𝑡)

7章 ヒープの条件の保持 HEAPIFYの動作例 16 4 4 10 14 7 9 3 14 2 8 8 1 1 2 3 i 4 4 5 6 7章　ヒープの条件の保持 1 16 2 3 i 4 4 4 10 4 5 6 7 14 7 9 3 14 8 9 10 2 8 8 1 HEAPIFYの動作例

7章 ヒープの条件の保持 HEAPIFYの動作例 16 14 4 10 4 7 9 3 14 2 8 8 1 1 2 3 4 4 5 6 7 7章　ヒープの条件の保持 1 16 2 3 14 4 4 10 4 5 6 7 i 4 7 9 3 14 8 9 10 2 8 8 1 HEAPIFYの動作例

7章 ヒープの条件の保持 HEAPIFYの動作例 16 14 4 10 8 7 9 3 14 2 8 4 1 1 2 3 4 4 5 6 7 7章　ヒープの条件の保持 1 16 2 3 14 4 4 10 4 5 6 7 8 7 9 3 14 8 9 10 2 8 4 1 HEAPIFYの動作例

7章 ヒープの条件の保持 𝑇 𝑛 ≤ 𝑇 2𝑛 3 +𝛩 1 HEAPIFYの実行時間は次の漸化式で表される。 7章　ヒープの条件の保持 HEAPIFYの実行時間は次の漸化式で表される。 分類定理の場合2からこの漸化式の解は 𝑂( lg 𝑛) となる。 𝑇 𝑛 ≤ 𝑇 2𝑛 3 +𝛩 1 𝑓 𝑛 =𝛩 𝑛 log 𝑏 𝑎 ならば 　　　　　𝑇 𝑛 = 𝛩 𝑛 log 𝑏 𝑎 lg 𝑛

7章 ヒープの構成 BUILD-HEAP(𝐴) 1 heap-size[𝐴] ← 𝑙𝑒𝑛𝑔𝑡ℎ[𝐴] 7章　ヒープの構成 BUILD-HEAP(𝐴) 1 heap-size[𝐴] ← 𝑙𝑒𝑛𝑔𝑡ℎ[𝐴] 2 for 𝑙 ← 𝑙𝑒𝑛𝑔𝑡ℎ 𝐴 /2 downto 1 do HEAPIFY(𝐴, 𝑖)

7章 ヒープの構成 BUILD-HEAPの動作例 4 4 16 1 1 3 3 14 2 2 16 16 9 10 10 14 14 8 8 7章　ヒープの構成 1 4 4 2 3 16 1 1 3 3 4 5 6 7 14 2 2 i 16 16 9 10 10 8 9 10 14 14 8 8 7 7 BUILD-HEAPの動作例

7章 ヒープの構成 BUILD-HEAPの動作例 4 4 16 1 1 3 3 14 2 2 16 16 9 10 10 14 14 8 8 7章　ヒープの構成 1 4 4 2 3 16 1 1 3 3 4 5 6 7 i 14 2 2 16 16 9 10 10 8 9 10 14 14 8 8 7 7 BUILD-HEAPの動作例

7章 ヒープの構成 BUILD-HEAPの動作例 4 4 16 1 1 3 3 14 14 2 16 16 9 10 10 14 2 8 8 7章　ヒープの構成 1 4 4 2 3 16 1 1 3 3 i 4 5 6 7 14 14 2 16 16 9 10 10 8 9 10 14 2 8 8 7 7 BUILD-HEAPの動作例

7章 ヒープの構成 BUILD-HEAPの動作例 4 4 16 1 1 10 3 14 14 2 16 16 9 10 3 14 2 8 8 7章　ヒープの構成 1 4 4 2 3 i 16 1 1 10 3 4 5 6 7 14 14 2 16 16 9 10 3 8 9 10 14 2 8 8 7 7 BUILD-HEAPの動作例

7章 ヒープの構成 BUILD-HEAPの動作例 4 4 16 16 1 10 3 14 14 2 16 7 9 10 3 14 2 8 8 7章　ヒープの構成 1 i 4 4 2 3 16 16 1 10 3 4 5 6 7 14 14 2 16 7 9 10 3 8 9 10 14 2 8 8 1 7 BUILD-HEAPの動作例

7章 ヒープの構成 BUILD-HEAPの動作例 16 4 14 16 1 10 3 14 8 2 16 7 9 10 3 14 2 8 4 7章　ヒープの構成 1 16 4 2 3 14 16 1 10 3 4 5 6 7 14 8 2 16 7 9 10 3 8 9 10 14 2 8 4 1 7 BUILD-HEAPの動作例

7章 ヒープの構成 BUILD-HEAPの全コスト 公式(3.6)より 7章　ヒープの構成 BUILD-HEAPの全コスト ℎ=0 lg 𝑛 𝑛 2 ℎ+1 𝑂 ℎ =𝑂(𝑛 ℎ=0 lg 𝑛 ℎ 2 ℎ ) 公式(3.6)より ℎ=0 ∞ ℎ 2 ℎ = 1/2 (1− 1 2 ) 2 =2 以上より、BUILD-HEAPの実行時間は𝑂(𝑛)で抑えることができる。

7章 ヒープソート HEAPSORT(𝐴) 1 BUILD-HEAP(𝐴) 2 for 𝑖 ← 𝑙𝑒𝑛𝑔𝑡ℎ[𝐴] downto 2 7章　ヒープソート HEAPSORT(𝐴) 1 BUILD-HEAP(𝐴) 2 for 𝑖 ← 𝑙𝑒𝑛𝑔𝑡ℎ[𝐴] downto 2 do 値の交換 𝐴[1] ↔ 𝐴[𝑖] heap-size[𝐴] ← heap-size[𝐴]-1 HEAPIFY(𝐴,1) ・HEAPSORTの手続きは、BUILD-HEAPの呼び出しに𝑂(𝑛)時間かかり 𝑛−1 回呼び出されるHEAPIFYは1回につき𝑂( lg 𝑛) 時間かかるので、𝑂(𝑛 lg 𝑛) 時間を要する。

7章　ヒープソート 16 14 10 8 7 9 3 2 4 1 ヒープソートの動作例

7章　ヒープソート 14 8 10 4 7 9 3 2 1 16 i ヒープソートの動作例

7章　ヒープソート 10 8 9 4 7 1 3 i 2 14 16 ヒープソートの動作例

7章　ヒープソート 9 8 3 4 7 1 2 i 10 14 16 ヒープソートの動作例

7章　ヒープソート 8 7 3 4 2 1 i 9 10 14 16 ヒープソートの動作例

7章　ヒープソート 7 4 3 1 2 8 i 9 10 14 16 ヒープソートの動作例

7章　ヒープソート 4 2 3 1 i 7 8 9 10 14 16 ヒープソートの動作例

7章　ヒープソート 3 2 1 4 i 7 8 9 10 14 16 ヒープソートの動作例

7章　ヒープソート 2 1 3 i 4 7 8 9 10 14 16 ヒープソートの動作例

7章　ヒープソート 1 i 2 3 4 7 8 9 10 14 16 ヒープソートの動作例

7章 プライオリティキュー 要素の集合Sを保持するためのデータ構造 各要素はキーを呼ばれる値を持つ。 7章　プライオリティキュー 要素の集合Sを保持するためのデータ構造 各要素はキーを呼ばれる値を持つ。 プライオリティキューには次の操作が可能である。 INSERT(S,x):集合Sに要素xを挿入する。 MAXIMUM(S):最大のキーをもつSの要素を返す。 EXTRACT-MAX(S):最大のキーをもつSの要素を削除してその値を返す。 プライオリティキューの1つの応用は計算機のジョブ割り当てである。 プライオリティキューは事象駆動のシミュレータでも利用される。 プライオリティキューはヒープを用いると効率的に実現することができる。

7章　プライオリティキュー HEAP-EXTRACT-MAX(𝐴) 1 if heap-size[𝐴] < 1 2 then error “ヒープのアンダーフロー” 3 𝑚𝑎𝑥 ← 𝐴[1] 4 𝐴[1] ← 𝐴[heap-size[𝐴]] 5 heap-size[𝐴] ← heap-size[𝐴] - 1 6 HEAPIFY(𝐴,1) 7 return 𝑚𝑎𝑥 HEAP-INSERT(𝐴,𝑘𝑒𝑦) 1 heap-size[𝐴] ← heap-size[𝐴] + 1 2 𝑖 ← heap-size[𝐴] 3 while 𝑖 > 1 かつ 𝐴[PARENT(𝑖)] < 𝑘𝑒𝑦 4 do 𝐴[𝑖] ← 𝐴[PARENT(𝑖)] 5 𝑖 ← PARENT(𝑖) 6 𝐴[𝑖] ← 𝑘𝑒𝑦

7章　プライオリティキュー 16 14 10 8 7 9 3 2 4 1 HEAP-INSERTの動作例

7章　プライオリティキュー 16 14 10 8 7 9 3 2 4 1 15 HEAP-INSERTの動作例

7章　プライオリティキュー 16 15 10 8 14 9 3 2 4 1 7 HEAP-INSERTの動作例

7章 プライオリティキュー HEAP-INSERTの動作例 ヒープを用いれば要素数nの集合に対するプライオリティキューの 7章　プライオリティキュー 16 15 10 8 14 9 3 2 4 1 7 HEAP-INSERTの動作例 ヒープを用いれば要素数nの集合に対するプライオリティキューの 任意の操作を𝑂( lg 𝑛) で実現できる。

8章 クイックソート クイックソートは最悪実行時間 𝛩(𝑛 2 )のソーティングアルゴリズムである。 8章　クイックソート クイックソートは最悪実行時間 𝛩(𝑛 2 )のソーティングアルゴリズムである。 にもかかわらず最もソーティングに用いられる。 なぜならば、平均実行時間は𝛩(𝑛 lg 𝑛)であり、定数部分がきわめて小さいからである。 さらにその場での(in place)ソーティングであることも利点のひとつである。

8章 クイックソートの記述 クイックソートはマージソートと同様に分割統治法に基づいている。 3つの分割統治のステップに分けて行う。 8章　クイックソートの記述 クイックソートはマージソートと同様に分割統治法に基づいている。 3つの分割統治のステップに分けて行う。 部分問題への分割：配列𝐴[𝑝..𝑟]を2つの部分配列𝐴[𝑝..𝑞]と 𝐴[𝑞+1..𝑟]に分割し、 𝐴[𝑝..𝑞]のどの要素も𝐴[𝑞+1..𝑟]の どの要素よりも小さいかまたは等しいようにする。 部分問題の解決：2つの部分配列𝐴[𝑝..𝑞]と𝐴[𝑞+1..𝑟]をクイック ソートの再帰呼び出しによってソートする。 部分問題の統合：2つの部分配列はその場でソートされてい るので、統合するためには何もする必要はなく、配列全 体𝐴[𝑝..𝑟]はソートされている。

8章　クイックソートの記述 QUICKSORT(𝐴,𝑝,𝑟) 1 if 𝒑<𝒓 2 then 𝑞 ← PARTITION(𝐴, 𝑝,𝑟) 3 QUICKSORT(𝐴,𝑝,𝑞) 4 QUICKSORT(𝐴, 𝑞+1,𝑟) PARTITION(𝐴,𝑝,𝑟) 1 𝑥 ← 𝐴[𝑝] 2 𝑖 ← 𝑝 -1 3 𝑗 ← 𝑟+1 4 while TRUE 5 do repeat 𝑗 ← 𝑗-1 6 until 𝐴[𝑗] ≤ 𝑥 7 repeat 𝑖 ← 𝑖+1 8 until 𝐴[𝑖] ≥ 𝑥 9 if 𝑖< 𝑗 10 then 値の交換 𝐴[𝑖] ← 𝐴[𝑗] 11 else return 𝑗

8章　クイックソートの記述 A[p..r] 5 3 2 6 4 1 3 7 j i PARTITIONの実行例

8章　クイックソートの記述 A[p..r] 5 3 2 6 4 1 3 7 i j PARTITIONの実行例

8章　クイックソートの記述 A[p..r] 3 3 2 6 4 1 5 7 i j PARTITIONの実行例

8章　クイックソートの記述 A[p..r] 3 3 2 6 4 1 5 7 i j PARTITIONの実行例

8章 クイックソートの記述 PARTITIONの実行例 A[p..q] A[q+1..r] 3 3 2 1 4 6 5 7 return j 8章　クイックソートの記述 A[p..q] A[q+1..r] 3 3 2 1 4 6 5 7 j i return PARTITIONの実行例

8章 クイックソートの記述 PARTITIONの実行例 配列𝐴[𝑝..𝑟]に対するPARTITIONの実行時間は𝛩(𝑛)である。 8章　クイックソートの記述 A[p..q] A[q+1..r] 3 3 2 1 4 6 5 7 j i return PARTITIONの実行例 配列𝐴[𝑝..𝑟]に対するPARTITIONの実行時間は𝛩(𝑛)である。

8章 クイックソートの性能 クイックソートの実行時間は分割が平均化されているか否かに依存し、また分割の際にどの要素を用いるかに依存する。 8章　クイックソートの性能 クイックソートの実行時間は分割が平均化されているか否かに依存し、また分割の際にどの要素を用いるかに依存する。 分割が平均化されているならば漸近的にマージソートと同じ実行時間で動作するが、そうでなければ漸近的に挿入ソートと同じ実行時間で動作する。

8章 クイックソートの性能 最悪の分割 クイックソートが最悪の振る舞いをするのは、分割手続きによって領域がn-1要素と1要素に分けられたとき 8章　クイックソートの性能 最悪の分割 クイックソートが最悪の振る舞いをするのは、分割手続きによって領域がn-1要素と1要素に分けられたとき n n 1 n-1 n 1 n-2 n-1 n 1 ・ 2 3 1 1 2 𝛩 𝑛 2

8章 クイックソートの性能 最良の分割 分割手続きによってサイズn/2の2つの領域に等分割されるとき n/4 n/4 n/4 n/4 n n 8章　クイックソートの性能 最良の分割 分割手続きによってサイズn/2の2つの領域に等分割されるとき n n n/2 n/2 n n/4 n/4 n/4 n/4 n 　　　・　　　　　　　　　・　　　　　　　　　・　　　　　　　　・ 　　・　・　　　　　　　・　・　　　　　　　　・　・　　　　　　・　・ 　・　　　・　　　　　・　　　・　　　　　　・　　　・　　　　・　　　・ lg n ・　・　・　・　　　　　　・・・　　　　　　・　・　・　・ 1 1 1 1 1 1 1 1 n 𝛩(𝑛 lg 𝑛)

8章 クイックソートの性能 平衡分割 クイックソートの平均実行時間が最悪の場合よりも最良の場合に近い 常に9:1で分割されると仮定 8章　クイックソートの性能 平衡分割 クイックソートの平均実行時間が最悪の場合よりも最良の場合に近い 常に9:1で分割されると仮定 n n n/10 9n/10 n log 10 𝑛 n/100 9n/100 9n/100 81n/100 n 　　　・　　　　　　　　　・　　　　　　　　　・　　　　　　　　・ 　　・　・　　　　　　　・　・　　　　　　　　・　・　　　　　　・　・ 　・　　　・　　　　　・　　　・　　　　　　・　　　・　　　　・　　　・ log 10/9 𝑛 n 1　　 　　　　　　　　　 　　　　　　　　　 　　　　　　　　・ 　　 　　　　　　 　　　　　　　　　　　　 ・ 　　　　　　　　　　　 　　　　　　　　　　　　　 ・ 1 ≤n 𝛩(𝑛 lg 𝑛)

8章 クイックソートの性能 平均的な場合に対する直観的説明 最良の分割と最悪の分割が交互に現れるとする。 (n-1)/2 (n-1)/2 n 8章　クイックソートの性能 平均的な場合に対する直観的説明 最良の分割と最悪の分割が交互に現れるとする。 n 𝛩(𝑛) 1 n-1 (n-1)/2 (n-1)/2

8章 クイックソートの性能 平均的な場合に対する直観的説明 最良の分割と最悪の分割が交互に現れるとする。 (n-1)/2 (n-1)/2 n 8章　クイックソートの性能 平均的な場合に対する直観的説明 最良の分割と最悪の分割が交互に現れるとする。 n 𝛩(𝑛) 1 n-1 (n-1)/2 (n-1)/2

8章 クイックソートの性能 平均的な場合に対する直観的説明 最良の分割と最悪の分割が交互に現れるとする。 (n-1)/2 (n-1)/2 n 8章　クイックソートの性能 平均的な場合に対する直観的説明 最良の分割と最悪の分割が交互に現れるとする。 n 𝛩(𝑛) 1 n-1 (n-1)/2 (n-1)/2 n 𝛩(𝑛) (n-1)/2 + 1 (n-1)/2

8章 クイックソートの性能 平均的な場合に対する直観的説明 最良の分割と最悪の分割が交互に現れるとする。 悪い分割は良い分割に吸収される。 8章　クイックソートの性能 平均的な場合に対する直観的説明 最良の分割と最悪の分割が交互に現れるとする。 n 𝛩(𝑛) 1 n-1 (n-1)/2 (n-1)/2 n 𝛩(𝑛) (n-1)/2 + 1 (n-1)/2 悪い分割は良い分割に吸収される。 実行時間は𝑂(𝑛 lg 𝑛)

8章　クイックソートの確率的アルゴリズム ここでは入力のすべての順列が当確率で現れるという仮定が成り立たなくてもうまく動作するクイックソートの２つの確率的アルゴリズムを示す。 乱数発生器RANDOMを用いた確率的アルゴリズム アルゴリズムの最悪時の動作を与える特定の入力は存在しないが、その代わりにアルゴリズムの最悪の場合は乱数発生器に依存する。 また、故意に良くない入力配列を作り出すことはできない。 最悪に近い動作をする順列はほとんど存在しない。 手続きPARTITIONの変形 配列を分割する前に要素𝐴[𝑝]と𝐴[𝑝..𝑟]からランダムに選ばれた要素とを交換する。 入力配列の分割は平均的にはバランスのとれたものになる。 解析はアルゴリズムの単純さほど簡単ではない。

8章　クイックソートの確率的アルゴリズム RANDOMIZED-PARTITION(𝐴,𝑝,𝑟) 1 𝑖 ← RANDOM(𝑝,𝑟) 2 値の交換 𝐴[p] ↔𝐴[𝑖] 3 return PARTITION(𝐴,𝑝,𝑟) RANDOMIZED-QUICKSORT(𝐴, 𝑝,𝑟) 1 if 𝑝<𝑟 2 then 𝑞 ← RANDOMIZED-PARTITION(𝐴,𝑝,𝑟) 3 RANDOMIZED-QUICKSORT(𝐴,𝑝,𝑞) 4 RANDOMIZED-QUICKSORT(𝐴, 𝑞+1,𝑟)

8章　クイックソートの解析 RANDOMIZED-QUICKSORTの解析 最悪の場合と平均的な場合の解析を行う。

8章 クイックソートの解析 ある定数cに対して𝑇 𝑛 ≤𝑐 𝑛 2 と推測 最悪の場合 置き換え法を用いて 𝑂(𝑛 2 )であることを示す。 8章　クイックソートの解析 最悪の場合 置き換え法を用いて 𝑂(𝑛 2 )であることを示す。 　ある定数cに対して𝑇 𝑛 ≤𝑐 𝑛 2 と推測 　 𝑇 𝑛 = max 1≤𝑞≤𝑛−1 𝑇 𝑞 +𝑇 𝑛−𝑞 +𝛩(𝑛) 𝑇 𝑛 ≤ max 1≤𝑞≤𝑛−1 𝑐 𝑞 2 +𝑐 (𝑛−𝑞) 2 +𝛩(𝑛) = 𝑐∙ max 1≤𝑞≤𝑛−1 𝑞 2 + (𝑛−𝑞) 2 +𝛩(𝑛) ここで、 max 1≤𝑞≤𝑛−1 𝑞 2 + (𝑛−𝑞) 2 ≤ 1 2 + 𝑛−1 2 = 𝑛 2 −2(𝑛−1)より 𝑇(𝑛) ≤𝑐 𝑛 2 −2𝑐 𝑛−1 +𝛩(𝑛) ≤ 𝑐𝑛 2 以上より、最悪の場合の実行時間は 𝛩(𝑛 2 )

８章　クイックソートの解析 平均的な場合 まず、分割の手続きがどのように動作するかを理解することによって、RANDOMIZED-QUICKSORTの平均実行時間を正確に解析する。 PARTITIONによって返されるqの値は𝐴[𝑝..𝑟]の要素の中での𝑥 = 𝐴[𝑝]のランクにのみ依存する。 𝐴[𝑝]を𝐴[𝑝..𝑟]のランダムな要素と入れ換えると、rank(𝑥) = 𝑖 となる確率は1/𝑛 rank(𝑥) = 1ならば、q=jが返されるとき、分割の小さい方は要素𝐴[𝑝]しか含んでいない。この確率は1/𝑛 rank(𝑥) ≥2ならば、PARTITION が停止したとき、分割の小さい方にあるrank(𝑥)-1 個の要素のいずれも𝑥より小さい。したがって、分割の小さい方の要素が𝑖である確率は1/𝑛 これらより、分割の小さい方のサイズ𝑞−𝑝+1が1となる確率は2/𝑛であり、 𝑖=1,2,…,𝑛に対してそのサイズが𝑖となる確率は1/𝑛

８章 クイックソートの解析 ここまでの議論から以下の漸化式が得られる。 ８章　クイックソートの解析 ここまでの議論から以下の漸化式が得られる。 𝑇(𝑛)= 1 𝑛 𝑇 1 +𝑇 𝑛−1 + 𝑞=1 𝑛=1 𝑇 𝑞 +𝑇 𝑛−𝑞 +𝛩(𝑛) 最悪時の解析から𝑇 𝑛−1 =𝑂 𝑛 2 なので 　　　　　　　　　　　 1 𝑛 𝑇 1 +𝑇 𝑛−1 = 1 𝑛 Θ 1 +𝑂 𝑛 2 　　　　　　　 =𝑂(𝑛) よって 𝑇 𝑛 = 2 𝑛 𝑘=1 𝑛−1 𝑇 𝑘 +𝛩(𝑛) ここから 𝑇 𝑛 = 1 𝑛 𝑞 𝑛−1 (𝑇 𝑞 +𝑇 𝑛−𝑞 ) +𝛩(𝑛) 　　　　が得られる。

８章　クイックソートの解析 𝑎>0,𝑏>0 に対して、𝑇 𝑛 ≤𝑎𝑛 lg 𝑛 +𝑏と仮定する。 このとき、𝑛>1 に対して、 𝑇 𝑛 = 2 𝑛 𝑘=1 𝑛−1 𝑇(𝑘) +𝛩 𝑛 ≤ 2 𝑛 𝑘=1 𝑛−1 (𝑎𝑘 lg 𝑘 +𝑏) +𝛩(𝑛) = 2𝑎 𝑛 𝑘=1 𝑛−1 𝑘 lg 𝑘 + 2𝑏 𝑛 𝑛−1 +𝛩(𝑛)

８章　クイックソートの解析 𝑘=1 𝑛−1 𝑘 lg 𝑘≤ 1 2 𝑛 2 lg 𝑛 − 1 8 𝑛 2 ⋯ ∗ を用いると、 𝑎 4 𝑛が 𝛩 𝑛 +𝑏 以上となるように𝑎の値を選べるので 𝑇 𝑛 ≤ 2𝑎 𝑛 1 2 𝑛 2 lg 𝑛 − 1 8 𝑛 2 + 2𝑏 𝑛 𝑛−1 +𝛩(𝑛) ≤𝑎𝑛 lg 𝑛 − 𝑎 4 𝑛+2𝑏+𝛩(𝑛) =𝑎𝑛 lg 𝑛 +𝑏+ 𝛩 𝑛 +𝑏− 𝑎 4 𝑛 よって、クイックソートの平均実行時間は𝑂(𝑛 lg 𝑛) である。

８章　クイックソートの解析 (*)の証明 𝑘=1 𝑛−1 𝑘 lg 𝑘 = 𝑘=1 𝑛/2 −1 𝑘 lg 𝑘 + 𝑘= 𝑛/2 𝑛−1 𝑘 lg 𝑘 ≤ lg 𝑛 −1 𝑘=1 𝑛/2 −1 𝑘 + lg 𝑛 𝑘= 𝑛/2 𝑛−1 𝑘 = lg 𝑛 𝑘=1 𝑛−1 𝑘 − 𝑘=1 𝑛/2 −1 𝑘 ≤ 1 2 𝑛 𝑛−1 lg 𝑛 − 1 2 ( 𝑛 2 −1) 𝑛 2 ≤ 1 2 𝑛 2 lg 𝑛 − 1 8 𝑛 2 より、𝑛≥2ならば(*)が成り立つ。