【このブログは執筆途中です】
１ はじめに
私がBig O Notationのことを初めて知ったのは、アメリカの大学院留学時代、言語学修士の学習をするかたわら、学部レベルのComputer Scienceの科目をせっせととっていたときでした。CS101というComputer Science専攻の学生たちがその一番最初の科目としてとる授業は、Pascalという教育言語を使って、プログラミングの基礎や基本的概念を徹底的に叩き込む内容でした。たしか、Big O Notationは、複数あるソート手法のそれぞれのefficiencyについて述べる箇所で出てきたように思います。
２ 概略
まずは、Big O notationについて、きわめておおざっぱに述べてみます。これはComputer Scienceの概念で、要素の数が大きくなった時にどれくらい時間およびメモリが消費されるかを示す値だとされています。
たとえば、n個の数字のうち、偶数がいくつあるかを調べる場合を考えてみます。n個の数字が与えられて、与えられた順に偶数か奇数かを判断していくとすれば、その判断はｎ回行われることになります。その場合のBig O Notationは、
O(n)
となります。
別の例で、n個の数字が与えられて、最初の数字について、それと残りの数字をそれぞれ掛け合わせるという作業をし、次の数についてもそれを残りの数字を掛け合わせる、ということを最後の数字まで行うことにします。掛け合わせる回数は、最初の数字については(n - 1)回、次の数字についても(n - 1)回、というふうにn個の数字について行われるから、掛け合わせる回数の合計は、n(n - 1)回ということになります。その場合のBig O Notationは、
O(n(n - 1))
となり、n(n - 1)) = - n においてnが無限大に近づくとき、- nは無視できると考えれば、
O()
となります。
O(n)とO()との違いは、グラフで見るとよくわかります。
下図で、赤線がy=x、青線がy=のグラフです。xが大きくなるにつれて、赤線と青線のyの値の差が大きくなってきます。つまり、n→
において、O(n)よりもO()の方が時間とリソースの消費量がはるかに大きいことになります。
３ より詳細な説明
ここまでは、私の記憶の範囲での話ですので、厳密でなかったり間違っていたりするかもしれませんので、いろんな文献をもとに、もう少し詳しく見ていきたいと思います。