アルゴリズムとは
- 問題を解くための手順
アルゴリズムの備える性質
- **【正当性】**入力に対してアルゴリズムの与える出力が,確かに与えられた問題の解であること
- **【有限性】**有限の時間で出力すること
- **【停止性】**任意の入力に対してアルゴリズムが停止すること
- **【決定性】**同じ入力に対して同じ出力を与えること
- 手続き中にランダム性を取り入れた,乱択アルゴリズムというものもある
- 素数判定アルゴリズムが有名.ランダム性を取り入れることで,「間違える可能性もあるけどとても低い」実用上耐えるアルゴリズムを考えることができる
- 手続き中にランダム性を取り入れた,乱択アルゴリズムというものもある
計算量complexity
-
時間計算量:アルゴリズムが出力を出すまでにどのくらい計算時間を要するか
- プログラムでアルゴリズムを書き下した時の,それぞれの文が何回実行されるのかで定量的に計る
- 空間計算量:アルゴリズムが出力を出すまでにどのくらいのメモリを必要とするか
- 平均・最良・最悪
計算量の漸近的な評価
- 問題のサイズ$n$に対する計算量の漸近的な振る舞いを以ってアルゴリズムの効率の良さを表現する
- $O$記法
O記法
- アルゴリズム$f(n)$(ここで$n$は問題のサイズ)の$n\rightarrow \infty$とした時の漸近的な振る舞いを書き下す記法
O(・)
$f(n) = O(g(n))$の時,$f(n)$は$g(n)$によって漸近的に上から抑えられる.
要するに,$f$は$n$がいくら大きくなったところで$g$を超えることができない.
具体例
- $O(1)$
- 問題のサイズが何倍になろうとも,そのアルゴリズムは一定の計算量で結果を出力するという意味.
- 例えば,問題のサイズが$5$倍になれば出力を得るまでに要する計算量が$1$倍になるということ.
- $O(n)$
- 問題のサイズに比例して計算量がかかる.
- 例えば,問題のサイズが$5$倍になれば出力を得るまでに要する計算量が$5$倍になるということ.
- $O(n^2)$
- 問題のサイズの二乗に比例して計算量がかかる.
- 例えば,問題のサイズが5倍になれば出力を得るまでに要する計算量が25(=$5^2$)倍になるということ.
- $O(\log n)$
- 問題のサイズの対数に比例して計算量がかかる.
- 例えば,問題のサイズが$5$倍になれば出力を得るまでに要する計算量が$2.32$(=$\log_{2} 5$)倍になるということ.
- $O(n \log n)$
- 「問題のサイズ」×「その対数」に比例して計算量がかかる.
- 例えば,問題のサイズが$5$倍になれば出力を得るまでに要する計算量が$11.6$(=$5\log_{2} 5$)倍になるということ.
- $O(2^n)$
- 問題のサイズの$2$の指数乗に比例して計算量がかかる.
- 例えば,問題のサイズが$5$倍になれば出力を得るまでに要する計算量が$32$(=$2^5$)倍になるということ.
- $O(n!)$
- 問題のサイズの階乗に比例して計算量がかかる.
- 例えば,問題のサイズが$5$倍になれば出力を得るまでに要する計算量が$120$(=$5!$)倍になるということ.
Θ(・)
$f(n) = \Theta(g(n))$の時,$f(n)$は$g(n)$によって漸近的に下から抑えられる.
要するに,$f$は$n$がいくら大きくなったところで$g$を下回ることができない.
Ω(・)
$f(n) = O(g(n))$の時,$f(n)$は$g(n)$によって漸近的に上下から抑えられる.
要するに,$f$は$n$がいくら大きくなったところで$g$とだいたい同じ感じになる.