計算量（けいさんりょう）とは｜意味・使い方・読み方解説

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

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

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

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

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

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

計算量けいさんりょう

IT

この用語ようごを学まなべるコンテンツ

関連かんれんする用語ようご

IT