４−３：高度なソートアルゴリズム�@ （分割統治法にもとづくソート）

内容

1. スライド　1 ４−３：高度なソートアルゴリズム�@（分割統治法にもとづくソート）
2. スライド　2 クイックソート
3. スライド　3 クイックソートの方針
4. スライド　4 説明上の注意
5. スライド　5 クイックソートの動き前半（分割１）
6. スライド　6 １
7. スライド　7 クイックソートの動き後半（再帰）
8. スライド　8 練習
9. スライド　9 クイックソートの実現１（分割）
10. スライド　10 クイックソートの実現2(再帰）
11. スライド　11 命題Ｑ１（クイックソートの停止性）
12. スライド　12 q_sort(left,left+k)の停止性を考える。
13. スライド　13 １２で呼び出すｑ（pos+1,left+k)において、 その適用される列の長さ...
14. スライド　14 停止しないクイックソート
15. スライド　15 命題Ｑ２（クイックソートのの正当性１）
16. スライド　16 命題Ｑ３（クイックソートのの正当性２）
17. スライド　17 クイックソートの計算量
18. スライド　18 クイックソートの最悪計算量
19. スライド　19 クイックソートの平均時間計算量
20. スライド　20 漸化式の導出
21. スライド　21 したがって、入力順列がすべて均等に起こるという仮定では、 クイックソートの平均...
22. スライド　22 漸化式の解法
23. スライド　23 次に、
24. スライド　24 両辺の差をとる。
25. スライド　25 ここで、
26. スライド　26 調和級数の見積もり
27. スライド　27 以上より、クイックソートの平均計算時間量は、 である。
28. スライド　28 マージソート
29. スライド　29 マージソートの方針
30. スライド　30 マージの動き
31. スライド　31 分割
32. スライド　32 マージソート動き前半（分割）
33. スライド　33 マージソート動き後半（マージ）
34. スライド　34 練習
35. スライド　35 マージに関する注意
36. スライド　36 データ退避の実現
37. スライド　37 マージの実現
38. スライド　38 マージソートの実現
39. スライド　39 命題Ｍ１（マージの正当性）
40. スライド　40 命題Ｍ２（マージソートの正当性）
41. スライド　41 命題Ｍ3(マージソートの停止性）
42. スライド　42 マージソートの計算量
43. スライド　43 解析を簡単にするため、データを 個あると仮定します。
44. スライド　44 　　　　　　　　であるような一般の入力サイズに対しては、 もう一段階解析の途中...
45. スライド　45 結局、どのような入力に対しても、マージソートの 最悪時間計算量は、 ...
46. スライド　46 分割統治法について
47. スライド　47 分割統治法とは
48. スライド　48 分割統治法のイメージ
49. スライド　49 分割統治法の時間計算量
50. スライド　50 一般的な分割統治法における時間計算量　　　は、次の漸化式で表されることが多い。
51. スライド　51 　　と　　　の大小関係で式が異なる。
52. スライド　52 場合１：
53. スライド　53 場合２：
54. スライド　54 場合３：
55. スライド　55 分割統治法の計算時間のまとめ