この記事を読んで分かること
- 計算量とは何か
- 計算量と処理時間の関係
計算量とは
計算量とは、
です。
プログラムがどのくらいの時間で実行が終わるかの目安になります。
計算量は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!)\)の増え方が大きいことが一目でわかりますね。
参考文献
コメント