アルゴリズムの高速化

内容

1. スライド　1 アルゴリズムの高速化
2. スライド　2 アルゴリズムにおける大幅な性能アップ
3. スライド　3 最大公約数問題
4. スライド　4 最大公約数問題
5. スライド　5 素朴な最大公約数発見法
6. スライド　6 i
7. スライド　7 アルゴリズムnaive_gcd(a,b) 入力：a,b 出力：gcd(a,b...
8. スライド　8 アルゴリズムnaive_gcdの正当性は明らかなので省略する。（帰納法で証明もで...
9. スライド　9 ユークリッドの互除法
10. スライド　10 アルゴリズムeuclid_gcd(a,b) 入力：a,b(a>bとする。） ...
11. スライド　11 ユークリッドの互除法の動作
12. スライド　12 練習
13. スライド　13 ユークリッド互除法の正当性
14. スライド　14 証明
15. スライド　15 帰納：
16. スライド　16 　場合１：b=r+1のとき。
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 アルゴリズムrecucive_gcd(a,b) 入力：a,b 出力：gcd(...
31. スライド　31 フィボナッチ数列問題
32. スライド　32 フィボナッチ数列問題
33. スライド　33 漸化式と再帰アルゴリズム
34. スライド　34 再帰アルゴリズムの利点の一つに、 漸化式で表された数列を直接プログラム にす...
35. スライド　35 アルゴリズムfibo_recの正当性は明らかなので省略する。 アルゴリズム...
36. スライド　36 の最悪時間量
37. スライド　37 このように、 再帰アルゴリズムの 時間計算量は、 始め漸化式で導かれること...
38. スライド　38 この漸化式を解く。
39. スライド　39 問題の考察による高速化
40. スライド　40 配列を用いたアルゴリズム
41. スライド　41 アルゴリズムfibo_arrayの時間計算量
42. スライド　42 fibo_recが低速な理由
43. スライド　43 更なる高速化