計算量とは、計算によって解が求まるまでの手数のこと。
ある課題を解くやり方(アルゴリズム)はひとつだけではない。各アルゴリズムについて計算量を求め、それらを比較することで、より効率のよいアルゴリズムを判断することができる。ソートやサーチなどの評価でよく使われる。
計算にかかる時間や使用するメモリ量は環境に依存するが、手数はアルゴリズムの効率評価の目安となる。
計算量は「オーダ」とも呼ばれ、評価するための式として O-記法(ビッグオー記法/ランダウ記法)が用いられる。
アルゴリズムを表現した命令について、実行される回数や操作の種類(順次、分岐、反復)により、扱うデータ数N との関係性を O(Nの式) で表現する。
時間性能に着目する場合は、実行回数に処理時間を加味した時間計算量を使用する。どれくらいメモリが必要かを求めたものは、領域計算量や空間計算量などと呼ぶ。
用語: | アルゴリズム |
プログラミング一般のTips: |
アルゴリズムと計算量(オーダ) |