## アルゴリズムの効率性 --- ## 目的 --- ### 計算問題に対して効率の良いアルゴリズム を 探す / 作る / 活用する / 評価する --- # 効率性とは？ --- ### 定義案１ アルゴリズムは,プログラムとして実装して実際の入力インスタンスに対して速く走るとき,効率的であるという --- ### ３つの問題点 --- ### 問題点１ ### どこでどう実装するのか --- ### 素数判定アルゴリズム ある数$N$に対して, $2 < n < N$を満たす全ての自然数$n$で割り切れなかったら素数 --- ### $\sqrt{N}$以下の自然数に変えても判定できる さっきのよりは速い --- ### Javaでの実装（遅そうなアルゴリズム） ``` public class MyClass { public static void main(String args[]) { int n = 2; while(n < 6500) { boolean isPrime = true; for(int i = 2; i < n; i++) { if(n % i == 0) { isPrime = false; break; } } if(isPrime) { System.out.println(n); } n++; } } } ``` https://www.jdoodle.com/online-java-compiler --- ### Befungeでの実装(速そうなアルゴリズム) ``` 2>:1->1-00p::00g: v v%-g00::_v#!`\ -_$$.v ^g00_ v ^+1 < > :.^ ``` Step: 100,000,000 http://www.quirkster.com/iano/js/befunge.html --- ### プラットフォームや、実装方法などに依存してしまう。 --- ### 定義案１（再登場） アルゴリズムは,プログラムとして実装して実際の入力インスタンスに対して速く走るとき,効率的であるという --- ### 問題点２ ### 実際の入力インスタンスとは --- ### 問題点3 ### 入力のサイズの増減に対応していない --- ### 定義案２ アルゴリズムは,解析レベルで,全探索よりも本質的に良い最悪時性能を達成するとき,効率的であるという --- ## 最悪時性能とは --- ### 最悪の時間を基準にするのは厳しすぎる？ --- ### 平均の時間を調べる ランダムな入力インスタンスについての平均を出す --- ### ランダムは難しい --- ### 乱数発生器  原子核崩壊の様子などを観測して乱数を生成する --- ### 擬似乱数 擬似乱数を生成するアルゴリズムが存在して,それを使うことになる この生成アルゴリズムの解析になってしまう --- #### 実際の入力インスタンスはランダムではない --- ### 最悪の時間を基準にするのは厳しすぎる？ --- 一般的には 最悪の場合の解析が,アルゴリズムの効率性の指標となる --- ### 最悪時性能での評価が適当 --- ### 定義案２（再登場） アルゴリズムは,解析レベルで,全探索よりも本質的に良い最悪時性能を達成するとき,効率的であるという --- ### G-Sアルゴリズム $n!$個のマッチングがある中で全探索を行うのは大変だが G-Sアルゴリズムは$n^2$に比例する時間しか必要としない --- ### 効率性の簡単な指標として全探索がある 全探索に比べて改善されたアルゴリズムには何かしらの発見がある --- ### 数学的な解析によって導かれてる 実装した結果ではない --- ### 定義案２（再登場） アルゴリズムは,解析レベルで,全探索よりも本質的に良い最悪時性能を達成するとき,効率的であるという --- ### 曖昧でもある 「本質的に良い性能」とは？ --- ### 定義案３ アルゴリズムは,多項式の計算時間を持つとき,効率的であるという --- ### 多項式時間 --- サイズ$N$のすべての入力インスタンスに対して 計算時間が$cN^d$で抑えられるとする($c>0,d>0$) すなわち,計算時間が高々$N^d$に比例する --- ### 入力サイズの増減に対応できる 入力サイズが$N$から$2N$になったとき, 計算時間は$c2^dN^d$になるが, $d$は対数なので$2^d$も定数になる --- ### 定義案３ アルゴリズムは,多項式の計算時間を持つとき,効率的であるという --- ### 疑問点 $n^{100}$は非効率では？ $n^{1+0.02logn}$は効率的では？ --- ### Yes, but... --- ### 現実に通用するか --- 多項式時間アルゴリズムの存在する問題は, ほとんど例外なく,増加の仕方がほどほどの多項式に比例する計算時間を持つ --- 逆に 多項式時間アルゴリズムが知られていない問題は, 実際にはとても難しい --- ### 定義案３ アルゴリズムは,多項式の計算時間を持つとき,効率的であるという --- 効率性を知る上で驚くほど適合している --- ### 多項式と指数関数の増加率の違い ---  --- ### 究極の恩恵 --- 効率的なアルゴリズムが存在しない という概念を表現できる --- それぞれの問題は,効率的な解をもちうる問題とそうでない問題とに分けられる --- ### アルゴリズムの効率性 アルゴリズムは,多項式の計算時間を持つとき,効率的であるという