ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

計算量のO記法について解ってきたりきてなかったり

よくアルゴリズムの計算量(時間計算量)をO記法で書いているのを見ますが、あれってよく解らなかったんですよね。

O(n)とか、O(n^2)とか…。

しかし、最近、解ってきたような気がしないでもないので、そのまとめを記します。




時間計算量について

まず、時間計算量についてです。

これは要するに処理に要する時間なのですが、無論そんなものはマシンの性能に依存します。

まぁそれでも、逐次処理なら機械語にしたあと、
すべての処理に必要なクロック数をみて、それを時間計算量にすればマシンに依存はしないんでしょうけども、コンパイラ等の処理系には依存します。

また、いちいち機械語にしないと必要なクロック数というのはわかりません。


ではどうすればいいのか。
しかし、みなさん考えてみてください。

厳密に時間計算量を求めようとするからうまくいかないのです。

もっとアバウトに、アバウトに考えてみると、処理するデータの個数と処理時間がどのように関係しているのか?

それだけわかれば十分なのです。
(十分なのか!?)





O記法について

そこでO記法というものが登場します。
O記法というのはコンピュータの世界以外でも用いられる手法だそうで、簡潔にいうと多項式をそれに近い単項式にする記法です。

どのように簡潔にするのかは、厳密には定義があるらしいのですが、アバウトにやっていきましょう。

まず、多項式の中で一番次数が大きい項だけ抜き出します。
そしてその項の係数(定数の係数)を1にします。

それがO記法のO()の中に入る式です。

(ちなみに、変数が複数あれば、それぞれの一番次数が大きい項を抜き出して、各項の係数を1にするのですが、詳しいことはよく知りません。)

例えば 2x^2 + 10x + 1 をO記法で表すと、まず2x^2だけ抜き出して、係数を1にして、O(x^2)となります。

5x + 1 ならO(x)です。


この時点でお察しの方もいるかもしれませんが、二次関数はO(x^2)になり、一次関数はO(x)で表します。

式中に対数関数がでてくることもあるようなのですが、

例えば log[2] x + 5 はO(log[2] x)です。
ただし、log[2] x + x はO(x)になるみたいです。

どういうことかというと、次数が一番大きい項を抜き出すというルールがありましたが、
これは厳密にいうと発散速度が一番速い項を抜き出すというルールだからです。

対数関数の発散速度は定数関数 < 対数関数 < 一次関数)という関係にあるため、このようになったのです。

ちなみに、x × log[2] x とかいう項もあって、これは一次関数より若干速く発散します。


また、さっきからlog[2]と書いてきましたが、情報系で使うO記法中の対数関数は、圧倒的に2を底とすることが多いため、省略してlogとしても底は2と解釈されるようです。


O記法の説明は以上です。
一番発散速度が速い項というのは、たいてい次数の大小比較でわかるでしょうけど、判断しづらい場合はWikipediaで表を見ましょう。




プログラムの時間計算量をO記法で表す

では実際に高級言語で記述されたアルゴリズムの、計算量をO記法で表してみます。


実は私がよくわからなかったポイントというのはここなのです。

O記法というのがどんなものか解っても、実際にプログラムの計算量をどのようにO記法で表せばいいのかがわからなかったのです。


さて、ここで線形探索のプログラムを(相変わらずC#で)書きます。


int LinearSearch(int[] array, int term)
{
for(int i = 0; i < array.Length; ++i)
{
if(array[i] == term) return i;
}

return -1; // 見つからず
}


このプログラムの計算量を考えてみます。

しかし、このアルゴリズムの計算量は場合によって違ってしまいます。

forループ一回分の計算量をaとしたとき、 array[0] == term なら計算量はaですし、array[9] == termなら計算量は10aです。

全ての場合において考えてみると、計算量はa, 2a, 3a…のいずれかとなり、最大でarray.Length × aとなります。


このように計算量が定まらない場合は、最大のものをアルゴリズムの計算量とするようです。

つまり、array.Length × aです。
array.Length = n とすると、anです。

よって計算量はanですが、aは定数であるためO記法で表すと計算量はO(n)となります。


要するに、こういうことなのです。

上記の定数aがいくつなのかといわれても、そんなことはわからないし、わからなくていいのです。

一番重要なことは計算量がnに比例するということだけです。

なぜかというと、nがかなり大きくなったときにaがいくつであってもあまり計算量に変わりはないから、というわけです。


このように、O記法のおかげでプログラムから計算量を考えることがとても用意になりました。

forループをネストしていても、O(n^2)だな、とかO(mn)だな、とか判別できますね。

二分探索のように対数関数が登場する場合は少し判断が難しいですけどね。

まぁ、そこは経験でなんとかなると思います。
アルゴリズムって同じようなものが多いので。




まだ、解ったり解らなかったりしている状態で書いた記事なので、説明が不明瞭な部分もあるかもしれませんが、その際はご指摘くださりますと幸いです。

奥が深いんですよね。本当に。

tag: 計算量 アルゴリズム 処理速度

コメント

成長したねぇ~
おじさん(15だけど)君がなにをいってるかさっぱりわからんよ…
なんかすごいもの作れそう
がんばれ!

  • 2014/06/20(金) 14:56:51 |
  • URL |
  • まっちゃ #-
  • [ 編集 ]

Re: まっちゃ

おじさん、ありがとう!(1歳差だけど)
まだ理解が足りない部分も多々ありますけどね~。

おじさん(まっちゃさん)もまだまだいけるはずです、頑張って!

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/348-ce344f26
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。