今回はプログラムの計算量について触れていこうと思います。
計算量とは、大まかにはプログラムの計算効率を測る指標のようなものです。
プログラムの処理には計算や、繰り返し、比較などの様々な処理がありますが、これらの処理はデータがどれぐらい増えたらどれぐらいの割合で実行時間が増えていくのかを表したりします。
計算量には2つの指標があります。
計算量の指標
ここでは、計算量の指標を見ていきます。
時間計算量
時間計算量はアルゴリズムを実行するときに消費する時間やステップ数がどれくらい必要なのかを指標とするものです。
計算量というとこの後に説明する空間計算量よりも時間計算量の方が一般的です。
時間計算量
空間計算量はアルゴリズムを実行するときに消費するアルゴリズムの処理に必要な空間的領域の大きさがどれくらい必要なのかを指標とするものです。
ビット、バイト、ワードなどを測るものです。
ただし、空間計算量は端末によって変化したり、パソコンのメモリは大幅に増えているので比較対象として定量化するのは難しくなっています。 なので、計算量というとまずは時間計算量のことだと認識した方がいいかもしれないです。
オーダー記法
ここからは計算量を具体的にはどうやって測るのかについて説明しようと思います。
計算量は一般に、オーダー記法（ビッグオー記法）と呼ばれるものを使用することで、どれぐらい計算量が必要になるのかというのを表すことができます。
ただし、プログラムの処理は実行マシンやメモリ容量、プログラミング言語などによって影響されるため、厳密な計算量は計れません。 なので、オーダー記法というのはあくまでも指標と思ってください。
そして、オーダー記法は O(1)やO(N2)などの表記で表されます。
ここで出てくる(1)や(N2)はデータの個数を表しています。
例えば 、O(N)は入力が2倍になれば計算量も2倍になるという意味です。
for文で繰り返す場合などが当てはまります。
O(N2)は入力が2倍になれば計算量は4倍になるという意味です。
2重for文で繰り返す場合などが当てはまります。
次の順で性能が良いとされています。(O(1)の方が性能がいい)
O(1) > O(logN) > O(N) > O(N2) > O(N3)
計算量を求める
では、実際に計算量を求める方法についてです。 ここでは、アルゴリズムの基本構造の単位で計算量を求めます。
順次
順次構造は今の処理が終わってから次の処理に進むという構造です。 プログラミングでは基本的に上の行から下の行まで順番に処理されます。
命令が順次に並んでいる場合は、合計ステップ数は、ステップ数を足したものになります。
計算量は、入力サイズの増減に関わらず一定なので、O(1)と表します。
反復
反復は繰り返し処理のことです。計算量は複数のパターンがあります。
①
for (int i = 0; i < n; i++) { // nは入力サイズとする
count++; // n回実行される
}
この場合には、合計ステップ数は入力サイズになり、計算量はO(N)と表します。
②
for (int i = 0; i < n; i += 3) { // nは入力サイズとする
count++; // n/3回実行される
}
この場合には、合計ステップ数はn/3になり、n/3回ループするので、計算量はn/3なので、O(N)と表します。 ここでなぜ計算量がO(N)になるのかは後で説明します。
③
for (int i = 1; i <= n; i = i * 2) {
count++; // logn回実行
}
この場合には、合計ステップ数はlognになり、計算量はO(logn)と表します。
このように処理の条件が変わると計算量も変わります。
分岐
分岐とはif文のことです。 分岐の場合にはより計算量の大きい方に分岐するものとして、ステップ数を求めます。
if (count > 0) {
// A処理
} else {
// B処理
}
例えば、上記のような分岐があったとします。
A処理とB処理でステップ数を比較して大きい方が分岐でのステップ数となります。 なので、計算量も比較して大きい方となります。
これらのステップ数や計算量を使用して合計を求めます。
計算量のルール
計算量を求める際には、ルールがあるので注意してください。
①最大次数の高事項以外を除く
計算量を求める際は、低次項を無視して最大次数の項だけを計算量として表します。 例えば、O(N2+N)という計算量があった場合、低次項を除いて、O(N2)が計算量となります。
f(x)=x2+10xを考えるとxが10あたりからx2の値が大半を占めることになります。 つまり、入力サイズが大きくなるにつれ、低次項の重要性が低くなっていくので、最大次数の項だけを計算量とします。
②定数係数は無視する
そして、定数係数は無視します。 例えば、O(2N)やO(3N)は定数倍の違いしかないため、係数部分を無視して、いずれもO(N)として扱います。
反復の際に、計算量がn/3なのをO(N)と表していたのはこのルールに基づいているからです。
まとめ
計算量に触れましたが、まだまだ導入部分だと思っています。 しかし、ここを理解すると実コードでどのような処理を書くべきか、このコードは改善した方がいいなどの判断基準を持つことができます。
