Thinkers'Studio
JavaとC言語の自習ツール
計算量(オーダ) (用語集)

計算量(オーダ)

 計算量とは、計算によって解が求まるまでの手数のこと。

 ある課題を解くやり方(アルゴリズム)はひとつだけではない。各アルゴリズムについて計算量を求め、それらを比較することで、より効率のよいアルゴリズムを判断することができる。ソートやサーチなどの評価でよく使われる。
 計算にかかる時間や使用するメモリ量は環境に依存するが、手数はアルゴリズムの効率評価の目安となる。

 計算量は「オーダ」とも呼ばれ、評価するための式として O-記法(ビッグオー記法/ランダウ記法)が用いられる。
 アルゴリズムを表現した命令について、実行される回数や操作の種類(順次、分岐、反復)により、扱うデータ数N との関係性を O(Nの式) で表現する。

 時間性能に着目する場合は、実行回数に処理時間を加味した時間計算量を使用する。どれくらいメモリが必要かを求めたものは、領域計算量や空間計算量などと呼ぶ。

関連ページ
用語: アルゴリズム
プログラミング一般のTips: アルゴリズムと計算量(オーダ)


ページTOP