オーダーについて知っておくべき5つのこと

研究室のゼミ発表で，「オーダーのことはよく分かっていませんが…」という前置きで計算量の見積もりをしているものを，昨年，今年と見かけました．
この日記が役に立つか，余計な御世話になるか分かっていませんが，ここに整理を試みてみました．

1. ビッグ・オー記法

「アルゴリズムの計算量をオーダーで表してみなさい」と指示されたときのオーダーは，

注文，発注という意味でもなく，
順番*1，順序，秩序という意味でもなく，
「百万のオーダー」*2というような使い方でもなく，
数学の位数という意味でもなく，

ビッグ・オー記法，あるいはwikipedia:ランダウの記号を用いて表すものを言います．

2. 一番次数の高いもの以外，それと係数は無視

ビッグ・オー記法では，基本的に，一つの文字に関するできるだけ簡単な数式に，「O( )」をかぶせます．このとき，

複数の項の足し算なら，次数の最も高いものだけを残し，他を取り除き，
定数倍の係数を，取り除きます．

例えば， $2n^2+5n+3=O(n^2)$ となります．
また， $10000n^{10}+2^n=O(2^n)$ です．どんな多項式関数よりも，指数関数のほうが， $n$ を十分大きくすれば*3，大きい値になるためです．
次数については，主要なものを覚えましょう．
定数＜ $\log n$ ＜ $n$ ＜ $n\log n$ ＜ $n^2$ ＜ $n^3$ ＜ $2^n$ ＜ $3^n$ ＜ $n!$
それぞれに「O( )」をかぶせることができます．なお，定数のオーダーは「O(1)」と書きます．
「アルゴリズムを改善する」とは，オーダーを小さくするようなアルゴリズムを見つけることと等価です．

3. 順次と分岐は，大きいほう

一つのアルゴリズムが，複数の処理で表わされるとき，全体としてどんなオーダーになるかについては，ダイクストラのwikipedia:構造化プログラミングで使われる，「順次」「反復」「分岐」のそれぞれで考え，ボトムアップに構成するといいでしょう．
順次と，分岐については，それぞれのオーダーを求めて，その大きいほうを選んでください．3つ以上あれば，その中で最大のもの一つを選べば，それがそこでのオーダーです．
一つのプログラムが3つのサブルーチンコールによって構成されていて，各サブルーチンの時間計算量が $O(n^2)$ ， $O(n\log n)$ ， $O(n^4)$ となっていれば，全体のオーダーは， $O(n^4)$ です．これを $O(n^2)+O(n\log n)+O(n^4)$ = $O(n^4)$ と表記してもかまいません．
(同日追記) 「if (condition(x)) printf("yes\n"); else printf("no\n");」のように，分岐のための条件判定に大きなコストがかかる場合は，「条件判定のための値(真偽値など)を求める処理」を条件判定の前に出し，「y=condition(x); if(y) 以下略」のようにすることで，条件判定そのものを $O(1)$ にすることができます．この例でのオーダーは，condition(x)の計算に関するそれになります．

4. 反復は，掛け算

反復については，掛け算です．反復回数が $O(f(n))$ であり，反復の1回あたりの処理の手間が $O(g(n))$ なら，その反復処理全体のオーダーは， $O(f(n)\cdot g(n))$ になります．ちなみに $O(f(n))\cdot O(g(n))$ = $O(f(n)\cdot g(n))$ は，数学のオーダーとしても正しい式です．
例えば，n行n列の行列の積を

  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      c[i][j] = 0;
      for (k = 0; k < n; k++) {
	c[i][j] += a[i][k] * b[k][j];
      }
    }
  }

と書いた場合*4，

kに関するfor文では，反復回数が $O(n)$ であり，「c[i][j] += a[i][k] * b[k][j];」の計算量は $O(1)$ なので，上で言う $f(x),g(x)$ は $n,1$ が対応し，全体としては $O(n\cdot 1)$ = $O(n)$
jに関するfor文では，反復回数が $O(n)$ であり，反復の中の1回の計算量は $O(1)+O(n)$ = $O(n)$ なので，全体としては $O(n\cdot n)$ = $O(n^2)$
iに関するfor文では，反復回数が $O(n)$ であり，反復の中の1回の計算量は $O(n^2)$ なので，全体としては $O(n\cdot n^2)$ = $O(n^3)$

となり，「n回の3重ループのオーダーは $O(n^3)$ 」という直観と合致します．

5. 何の数を基準として，どの操作に関する評価をしたいのか?

ここまで特に定義せず「 $n$ 」という表現を使ってきましたが，オーダーで表すときは，この $n$ を何と置くか，つまり何の数を基準としたオーダーなのかが，重要になってきます．
厳密には入力長なのですが，実際上は，入力長の定数倍以下で表現でき，取扱いのしやすい何らかの個数を使います．
ここでの「定数倍」は，1よりも小さい定数になります．例えばソーティングなら，「要素1個のサイズ×要素数=入力長」ですから，「要素1個のサイズの逆数」を掛けることで，ふだん使われる，「 $n$ は要素数」となります．
それと，どの操作に関する評価をしたいのかを決めておくことも，特にプリミティブな(最も内部の)処理のオーダーを求める際には，不可欠です．ソーティングなら，比較回数に着目します．

*1:「スターティングオーダー」という表現がありますね

*2:これで，1,000,000以上10,000,000未満を意味し，「十万のオーダー」よりも大きく「一千万のオーダー」よりも小さいことが分かるわけです．単位をつけて，「100Mbpsのオーダー」と表現することもあります．

*3:学生のときに読んだ英語の本で，「almost everywhere」という表現をとっているものがありました．「ほとんど至るところ」と訳します．そこでは，「有限個の例外を除いて」という意味でした．これは「あるNが存在し，n＞Nならその性質(関数の大小関係など)が成り立つ」ということで，「nを十分大きくすれば」と同じことを言っています．それ以降は見ることがなかったので，その本だけの表現だったのでしょう．なお，「almost everywhere」という概念そのものは，ルベーグ積分を学べば出てきます．「測度0のところを除いて」という意味だったかな．

*4:「行列の積は必ず3重ループ」というものではありません．疎な行列の計算では，それに応じた処理を書くほうが，効率が良くなります．

わさっきhb

大学（教育研究）とか，親馬鹿とか，和歌山とか，とか，とか．