O記法とは

2005年03月21日(月) 10時00分
今日は、できるだけ分かりやすく、楽しみながらO記法とソートを
ご紹介してみたいと思います。

例えば、トランプをするとき、ある特定の規則に
トランプの札を並べえたりしますね。
この並び替えをソートといいます。

トランプの並び替えにもいろんな方法があるように、
ソートのアルゴリズムにも、いろんな方法があります。
そして重要なのはどのアルゴリズムを選ぶかによって
速さが違ってきちゃうということです。

では、速さをはかる目安はどうするか。
アルゴリズムは、データ要素数Nについて、
いろいろな関数をとってしまうので、速さは
単純に比較しにくいですね。

そこで大雑把な処理時間を見積もるO記法(ビック・オー記法)
というものが用いられます。

O記法とは、影響度の小さい変数や定数を削除しちゃって、
最も影響度が大きいnの項をだけで表記する方法です。

例えば、計算量(回数)が、N+5回だとしたら、「O(N))」
計算量がN+N2回だとしたら、 「O(N2)」となります。
ね。とっても便利でしょ

この、O記法を使うことによって、アルゴリズムの計算量を
比較できるようになるのです


ここからは、ほんのちょびっとだけ難しくなるかもしれないですが
興味のある方は読んでみてくださいね。
ソートには、バブルソート、シェーカソート、単純選択ソート、
挿入ソート、ヒープソート等々いろいろな種類があります。

では、代表的なソートのアルゴリズムの計算量を考えてみましょう。
例えば、最も単純なバブルソートのオーダーはN2
O表記でいうなら、「O(N2)」ですね。

理由としては、ソートの要素をN個とすると、左から右までを探索する
処理でN回のループが走り、さらにそのループをN回分繰り返すから、
「O(N2)」になります。

※厳密には確定した箇所以外のループを回せばよいので、ループは
1/2N2回となりますが、定数は考えないから「O(N2)」となります。

では、クイックソートってどうして「O(Nlog2N)」になると 思いますか?

センス・オブ・プログラミングを引用しながら、
箇条書きで整理してみたいと思います。

さあ、はじまり、はじまり

1)クイックソートは、軸を決めて、配列を2分割しながら探索していく

2) 配列を2分割するとき、データ量が倍になったとしても、
 分割を行う回数は、1回増えるだけですむからデータ数が
  Nの場合、配列を2分割するのはlog2N回となる

3)配列を2分割するという処理1回にかかる時間は、配列のサイズ
  Nに比例する

∴クイックソートは、「O(Nlog2N)」になる


ちなみに、なんで対数関数を使ってるの〜って思った方のために
補足です

対数関数を使ってるのは、
・ 配列を2分割するという処理をN回行うとすれば、2n(指数関数)
 サイズの配列が分割できる

・ 要素数Nの配列を分割するには何回分割を行えばいいかは
 この逆を計算すればよいから、指数関数の逆関数である
 対数関数(log)を使う

というわけです。
ちょっぴりでも、なるほどと思ってくれた人はこちらへ

一生懸命書いてたら、なんだか眠くなってしまいました。
今日は休日だし出かける前に、お昼ねしちゃおうかな
  • URL:http://yaplog.jp/love_rabbit/archive/43