概要
この記事では計算量の導出について紹介します。
オーダー記法シリーズの中でも最も面白く、知るべき内容だと思います。
この記事では特に線形探索と二分探索の計算量を導出します。
この2つの導出を見るだけでも、基本的なテクニックが詰まってますので応用がききます。
また、この記事の内容は動画にもまとまっていますので、
より理解を深めたい方はぜひご覧ください。
線形探索の計算量を導出する方法を説明した動画
二分探索の計算量を導出する方法を説明した動画
計算量の導出
計算量の導出はどのように行うかというと、
定数時間の計算を何回行う必要があるかを数えることで出来ます。
問題の入力で使われる変数を使って定数時間の計算を
何回行うのかを表していきます。
線形探索と二分探索の場合は、入力のリスト長である n を
使うことで計算量を表現できることが分かっています。
それでは早速、線形探索の計算量を導出します。
線形探索の計算量の導出
では早速、線形探索の最悪時間計算量を導出します。
線形探索の手続きを思い出してみましょう。
linear_search(e, a, n)
iを0とするa[i]がeと等しければiを返して終了、そうでなければ手順3に進むiに1を足してiがn以上であれば-1を返して終了、そうでなければ手順2に戻る
手順1の計算量は、代入を1回だけ行っているので O(1) です。
手順2の計算量は、配列の参照＋比較を行うので O(1 + 1) = O(2) = O(2 * 1) = O(1) です。
計算量の性質のうち、「係数は消していい」を適応しました。
手順3の計算量は、足し算＋比較を行うので O(1 + 1) = O(2) = O(2 * 1) = O(1) です。
また計算量の性質のうち、「係数は消していい」を適応しました。
あとはそれぞれの手順が、最悪の場合に何回行われるかを計算します。
手順1は1回だけです。
手順2は比較して等しければアルゴリズムが終了してしまいます。
最悪の場合というのは、等しくなくて手順3に進むケースです。
言い換えると、探している要素が配列内にない場合です。
この場合、手順2は n 回実行されます。
手順3も同様に、最悪の場合は n - 1 回実行されます。
ここまで計算した、各手順の計算量に、その手順が実行される回数をかけて、足します。
O((1 * 1) + (1 * n) + (1 * (n - 1))) これが線形探索の最悪時間計算量です。
あとは、計算量の性質を使って簡単にしていきます。
O((1 * 1) + (1 * n) + (1 * (n - 1))) = O(1 + n + n - 1) = O(2n) = O(n) となります。
以上で、線形探索の最悪時間計算量が導出できました。
二分探索の計算量の導出
続いて二分探索の最悪時間計算量を導出します。
binary_search(e, a, imin, imax)
- もし
imax < iminであれば-1を返す。そうでなければ手順2に進む - リストの探索範囲の真ん中の番号を
imid <- imin + (imax - imin) / 2とし、真ん中の要素をmid <- a[imid]とする - もし
mid > eであれば現在の探索範囲の左半分が次の探索範囲となるためbinary_search(e, a, imin, imid - 1)を返す。そうでなければ手順4に進む - もし
mid < eであれば現在の探索範囲の右半分が次の探索範囲となるためbinary_search(e, a, imid + 1, imax)を返す。そうでなければ手順5に進む mid = eであるため、imidを返す
二分探索は、二分探索中に二分探索を行う再帰的なアルゴリズムなので、
まずは1回の二分探索を実行した際にかかる計算量を導出します。
手順1は比較をおこなうので O(1) です。
手順2は代入＋四則演算＋配列の参照なので O(1) です。
手順3は比較＋二分探索ですが、今は二分探索の計算時間量を計算しているので、
比較にかかる O(1) だけを考えたいと思います。手順3も O(1) です。
手順4も同様に O(1) です。
手順5は代入なので O(1) です。
ということで、1回の二分探索にかかる計算量は O(1) です。
あとはこの二分探索が何回実行されるかを求めます。
最悪の場合、要素が見つからず何回も二分探索を行うことになりますが、
このときに二分探索は何回実行されるのか考えます。
たとえば n = 4 だとしましょう。
探索範囲は1回の二分探索で半分になっていくので、
4 -> 2 -> 1 -> 0 のように減っていきます。
これは n = 2^(m-1) だとすると m 回実行されるという法則になっています。
m を n で表すと、 m - 1 = log2(n) -> m = log2(n) + 1 となります。
つまり、二分探索は log2(n) + 1 回実行されます。
O(1) の二分探索を O(log2(n)) 回実行されるので、
最終的な最悪時間計算量は O(log2(n)) となります。
さいごに
以上でリスト探索の2つのアルゴリズムの最悪時間計算量を導出しました。
1. 線形探索の最悪時間計算量は O(n)
2. 二分探索の最悪時間計算量は O(log2(n))
アルゴリズムの計算量を導出するには、各手順の計算量と、
その手順が実行される回数をかけて足すことで導出できます。
この記事の中にも再帰的なアルゴリズムの計算量導出が含まれており、
このテクニックを応用すればほかの計算量も導出できると思います。
他のアルゴリズムやデータ構造についても紹介予定ですので、それは別の記事で紹介します。
