計算量けいさんりょう

計算けいさん量りょう（Complexity）は、アルゴリズムの実行じっこう時間じかん（時間じかん計算けいさん量りょう）やメモリ使用しよう量りょう（空間くうかん計算けいさん量りょう）を、入力にゅうりょくサイズ $N$ の関数かんすうで表あらわしたものです。データ量りょうが増ふえたときどれだけ処理しょりが重おもくなるかを比くらべるための指標しひょうで、O 記法きほう（オーダ記法きほう） で表あらわします。

オーダ	呼よび名な	代表だいひょう例れい	N が増ふえたとき
$O\left(1\right)$	定数ていすう時間じかん	配列はいれつの添字そえじアクセス	変かわらない
$O(\log N)$	対たい数すう時間じかん	2 分探索2 ぶんたんさく	ほとんど増ふえない
$O\left(N\right)$	線形せんけい時間じかん	線形探索せんけいたんさく	比例ひれいして増ふえる
$O(N\log N)$	準じゅん線形せんけい	マージソート	やや速はやく増ふえる
$O\left(N^2\right)$	2 乗じょう時間じかん	バブルソート	急激きゅうげきに増ふえる

評価ひょうかは通常つうじょう、最もっとも処理しょりが重おもくなる 最悪さいあく計算けいさん量りょうで行おこないます。たとえば $O\left(N^2\right)$ のアルゴリズムを $O(N\log N)$ に改善かいぜんできれば、データが大量たいりょうのとき劇的げきてきに速はやくなります。

ポイント 計算けいさん量りょうはデータが多おおいときの差さを表あらわすため、N が小ちいさいうちは差さが出でにくいことに注意ちゅうい。O 記法きほうでは係数けいすうや定数ていすう項こうを無視むしします。