ビッグオー記法解説!

アルゴリズムの勉強をしていて、ビッグオー記法が出てきて、文系の僕には初見で難しかったので、備忘録として書きました。

ビッグオー記法とは

簡潔に言えば、アルゴリズムがどれくらい高速であるのかを表す特別な表記法。

ex) O(n)  O(n!) など

なぜ使うのか

例を使って説明します

100個のリストの中から、「単純探索」と「二分探索」を使って、任意の要素を検索する際の時間を考えます。

1つの要素を調べるのに、1ミリ秒かかるとします。

単純探索

100個全ての要素を調べる必要があるので、100ミリ秒かかる。

二分探索

log2 100 なので、7ミリ秒しかかからない。

 

単純探索の方では、要素が増えるたびに時間が要素分増えていきます。

逆に二分探索の方は、リストの要素数が増えれば増えるほど、速度は加速していきます。

上記のことから、単純探索と二分探索は同じレートで加速しないということです。

上のように、具体的な計算時間量を知っておくだけでは不十分なので、より抽象的な式を知っておく必要があります。そこで、登場するのがビッグオー記法です。

 

特徴

いつくかの特徴があります。

1 ビッグオー記法では、秒数を表さない。演算の個数を比較できるようにする

2 最悪の場合の時間計算量を定める

3 最大次数の項以外を省く

ex) O(n2 + n) => O(n2)

4 係数は省く

ex) O(2n) => O(n)

一般的な時間計算量

  • O(log n)
    • 対数時間とも呼ばれる。
    • ex) 二分探索
  • O(n)
    • 線形時間とも呼ばれる。
    • ex) 単純探索
  • O(n log n)
    • ex) 高速なソートアルゴリズム
  • O(n2)
    • ex) 低速なソートアルゴリズム
  • O(n!)
    • ex) 巡回セールスマンなどのような非常に低速なアルゴリズム

 

まとめ

上記のようなことを頭に入れておけば、アルゴリズムの時間計算量を考えることができます。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA