アルゴリズム入門
アルゴリズムとは
あることを達成するための手順のこと。コンピュータの世界では、データ処理、数値処理、組み合わせ計算、シミュレーションなどの問題を解決するための手順をアルゴリズムと呼ぶ。どのアルゴリズムを選択するかによって計算時間が大きく変化する。
計算量の評価
時間計算量(time complexity) - プログラムの実行に必要な時間を評価する。計算機のプロセッサをどれだけ利用するか見積もる。
領域計算量(space complexity) - プログラムの実行に必要な記憶領域を評価する。計算機のメモリをどれだけ利用するかを見積もる。
一般的には、システムの環境を考慮した上で時間計算量と領域計算量のトレードオフやバランスを考えてアルゴリズムを設計する。領域計算量よりも時間計算量の方が問題になることが多い。
プロセッサとは
プロセッサ (processor) は、コンピュータシステムの中で、ソフトウェアプログラムに記述された命令セット(データの転送、計算、加工、制御、管理など)を実行する(=プロセス)ためのハードウェアであり、演算装置、命令や情報を格納するレジスタ、周辺回路などから構成される。
O表記法
アルゴリズムの効率を評価する「ものさし」の一つがO表記法である。O(n)やO(n^2)のようにnを問題の入力サイズとした関数でアルゴリズムの効率を表す。O(g(n))は計算量がg(n)に比例することを意味し、「オーダーがg(n)である」と言う。
アルゴリズムの計算量は、最善、平均、最悪の場合について見積もることができる。平均の計算量が最悪の計算量と同等になる場合が多いことや、最悪の計算量を見積もればそれ以上の心配をする必要がないということから、一般的にアルゴリズムの設計においては最悪の計算量を見積もる。
表記 | 意味 | 例 |
---|---|---|
O(1) | 定数 | 配列を添字アクセスする場合 |
O(log n) | 対数 | 二分探索(【探索】第4章参照) |
O(n) | 1次 | 線形探索(【探索】第1章参照) |
O(n log n) | n log n | クイックソート(【整列】第8章参照) |
O(n2) | 2次 | 2重ループを伴う配列全体の走査。バブルソート(【整列】第3章参照)など |
O(n3) | 3次 | 3重ループを伴う配列全体の走査。行列計算など |
O(2n) | 指数 | 集合分割問題 |
この表で上の方にあるほど、計算量が小さい、効率的なアルゴリズムである。しかし、現実的には必ずしも、効率的なアルゴリズムほど高速であるとはいえないことに注意が必要である。まず、データの個数を表す n は、それなりの大きさがあることを前提としている。小さなデータ列を対象とすると、O(n) よりも O(n log n) の方が高速である可能性もある。しかし、データ列が大きくなっていけば、歴然とした差が出てくる。
計算量の比較
オーダーがO(√n)、O(logn)、O(nlogn)などのアルゴリズムはnが増加しても計算量はそれほど増加しないので効率が良いと言える。一方、オーダーがO(2^n)やO(n!)のアルゴリズムは、入力nが数十になっただけで計算量が何十桁にも至ってしまう。
重要なことは、プログラムを実装する前に、入力の上限からアルゴリズムの最悪の計算量を評価することである。計算量は、単純に「5秒掛かる」のような表現を取る訳ではない。そもそも「5秒」というのは、ある特定のマシン上での結果に過ぎず、他の環境で試せば大きく変動するので、性能評価の方法として適切とは言い難い。
そこで、「秒」のようなものを使わず、「命令数」のような方法を利用します。1命令を実行するための時間は環境によって異なっても、同じ言語で同じように実装されたアルゴリズムの命令数は変わらないので、これを基準とします
計算量を見積もり、そのプログラムが実用的であると判断できる基準は、計算の内容や実行環境等によって左右される。現在のコンピュータの処理速度を考えると、比較や基本演算などの計算回数が数百万から数千万程度以下であれば、数秒以内で処理を行うことができるだろう。
計算量の求め方
1.各行のステップ数を求める
int calculate(int n) { // nは入力サイズを表す int count = 0; // 1回実行 for (int i = 0; i < n; i++) { count++; // n回実行 } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { count++; // n^2回実行 } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { count++; // n^2回実行 } } return count; // 1回実行 }
2.各行のステップ数を足し合わせて、プログラム全体のステップ数を求める。
プログラム全体のステップ数=1+n+n^2+n^2+1 =2+n+2n^2
3.最大次数の項以外を除いた上でさらに係数を除く
2+n+2n^2→2n^2 2n2→n^2
最終的にこのコードの計算量は、O(n2)となる。
参考:最大次数の項と係数を除く理由、計算量による比較が万能でないこと等
https://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c
http://d.hatena.ne.jp/nowokay/20090106/1231233947