概要
この記事では「オーダー記法」と「計算量の比較」について説明します。
また、記事の内容は動画でも紹介していますので、よければ確認してください。
オーダー記法とは
オーダー記法は計算量を数学的に記述する方法です。
まずは具体例から紹介します。
例えば O(n) , O(log(n)) , O(n^2) のように表記します。
O() の中に数式を書くという決まりがあります。
Oは「程度」という意味のOrderという単語からきているそうです。
数式に使うのは、問題の入力に使う変数です。
例えばリスト探索であれば、 e , a , n が使えます。
線形探索と二分探索は n があればその計算量を表現できます。
ここで次のような問題について考えます。
- 問. 整列済みのリストを探索する場合、次の1と2のどちらが速いか？
- 線形探索
- 二分探索
ここでは2つのアルゴリズムの最悪時間計算量がすでに分かっている前提で、
どちらのアルゴリズムが速く問題を解くのか考えていきたいと思います。
つまり、2つの計算量を比較し、どちらが小さいのか考えます。
計算量が小さいということは、少ない時間で問題を解ける、つまり速いということになります。
ではここで2つのアルゴリズムの計算量を紹介します。
計算量を導出する方法については、別の記事で紹介します。
線形探索の最悪時間計算量は O(n) です。
二分探索の最悪時間計算量は O(log(n)) です。
さて、線形探索と二分探索のうちどちらが速いのか考えます。
計算量の比較
オーダー記法で表現された計算量を比較する際に重要な点があります。
それは、「数式の中で使われる変数が十分に大きくなった時について考える」ことです。
なぜか説明していきたいと思います。
例えばリスト探索のアルゴリズムでは、入力のリスト長 n が大きければ大きいほど計算時間量が大きくなります。
これは当然のことなのですが、こういった状況でも速く問題を解くことをアルゴリズムに要求したいのです。
なので、「数式の変数が大きい時に計算量が小さい」のが優秀なアルゴリズムであるということになります。
この考え方は、前の記事で 最良 ではなく 最悪 の状況を想定することが大事だと説明したことと似ています。
しかし、変数が大きい時の数式を評価するのは 平均 の状況でも変わりませんので注意しましょう。
さて問題に戻って考えてみましょう。
n が十分大きい時の、 log(n) と n を比較すれば良いです。
これについてはグラフを見て考えると簡単です。
グラフを見ると、「二分探索の方が線形探索より速い」と言えるのです。
では下記のようになるのはなぜでしょうか？
* 線形探索の最悪時間計算量は O(n)
* 二分探索の最悪時間計算量は O(log(n))
これを説明するには計算量の導出について別の記事で説明する必要がありますが、
その前に少し説明したいのが、「定数時間」と「計算量の性質」です。
定数時間と、計算量の性質
ここでは、計算量の性質を紹介します。
計算量の性質を正しく理解することは、計算量の導出に不可欠です。
少し抽象的な話になりますが、大事な部分ですのでゆっくり見てください。
定数時間( O(1) )は、計算量の単位となる最小の計算時間のことです。
アルゴリズムの計算量を導出するには、定数時間で行える計算を
どれくらい繰り返せば終了するかを考える必要があります。
まずは定数時間で行える計算をいくつか紹介します。
以下の計算は、定数時間( O(1) )で計算できます。
1. 配列の参照
2. 代入
3. 比較
4. 四則演算
いくつか注意事項があります。
・配列の参照は定数時間ですが、連結リストなど別のデータ構造ではまた別の計算時間になります
・四則演算も、厳密には演算する数の桁数によって時間計算量が変わりますが、
ただ、一般的に探索する配列の長さの方が大きくなるので、ここでは定数時間とします
実は、線形探索や二分探索は以上で紹介した定数時間の計算を
組み合わせたり繰り返すことで実現することができます。
あとは、計算量の性質について知れば、アルゴリズムの計算量を導出できます。
ということで、計算量の性質を説明したいと思います。
計算量の性質
- 最も大きくなる項だけを残す
- 係数は消していい
これまでも説明してきましたが、とにかく変数が大きいときの計算量に興味があります。
これがなぜか、実際に具体例を挙げて説明したいと思います。
例えばあるアルゴリズムの計算が、定数時間の計算を
3n^2 + 4n + 8 回することで終了することがわかったとします。
この時、計算量の性質1より、 3n^2 の項だけ残せば良いとなります。
他の 4n や 8 の項に比べて、 n が大きい時に大きくなるからです。
さらに性質2より、 3n^2 の項の係数である 3 が不要となります。
先ほどの説明でも伝わったと思いますが、係数は計算量にあまり影響しません。
ここまでで計算量の性質については以上となります。
この動画では下記の2点がポイントです。
- 定数時間という最小単位の時間で行える計算がある
- アルゴリズムの計算量は、定数時間の計算を何回ぐらい行うかで決まる
- 計算量の性質は、小さな項や係数は影響が少ないため無視するというもの
次回はついに計算量の導出について説明したいと思います。
