計算量(オーダー)とは?計算量オーダーの実用範囲を表で解説

スポンサーリンク
計算量(オーダー)とは?計算量オーダーの実用範囲を表で解説 アルゴリズム
この記事を読んで分かること
  • 計算量とは何か
  • 計算量と処理時間の関係

 

計算量とは

計算量とは、

アルゴリズムの効率を評価する1つの指標

です。

 

プログラムがどのくらいの時間で実行が終わるかの目安になります。

計算量はO記法を用いて表現することが一般的で、 \(O(N)\)や\(O(N^{2})\)のような標記方法をします。

\(O(N)\)では計算回数がNに比例し、\(O(N^{2})\)では計算回数が\(N^{2}\)に比例することを表します。

 

例えば、1からNまでの数字の合計を計算する際に、愚直に(\(1+2+3+…+N\))(\(1+2+3+…+N\))と計算すると、N回の足し算をするためO(N)になります。

プログラムを書くとこのようなアルゴリズムがO(N)です。

N = 10
ans = 0
for i in range(1, N + 1):
    ans += i

 

計算量の目安

計算量が求められると、入力データNの大きさからプログラムの実行速度を推測することができるようになります。

一般的なPCの計算速度は1Ghzとすると、1秒間におおよそ10億(\(10^9\))回計算することができます。

言語によって実行速度は異なりますが、C++であれば1秒間に10億回、pythonであればその1/10程度の1億回が目安となります。

1秒間に10億回までの計算量オーダーは以下のようになります。

計算量オーダー
N \(O(log_2{N})\) \(O(\sqrt{N})\) \(O(N)\) \(O(Nlog_2{N})\) \(O(N^2)\) \(O(2^N)\) \(O(N!)\)
5 3 3 5 15 25 32 120
10 4 4 10 40 100 1024 \(10^6\)
 20 5 5 20 100 400 \(10^6\) \(10^{18}\)
30 5 6 30 150 900 \(10^9\)
\(10^5\) 17 317 \(10^5\) \(10^6\) \(10^{10}\)
\(10^9\) 30 31623 \(10^9\) \(10^{10}\)
\(10^{18}\) 60 \(10^9\)

 

\(O(2^N)\)や\(O(N!)\)の計算量は爆発的に増えていくので、できれば避けてアルゴリズムを作成していきたいですね。

 

続いて計算量オーダーのグラフです。

計算量(オーダー)のグラフ

\(O(N^2)\)、\(O(2^N)\)、\(O(N!)\)の増え方が大きいことが一目でわかりますね。

 

参考文献

競技プログラミングの鉄則
created by Rinker

コメント

タイトルとURLをコピーしました