Hatena::ブログ(Diary)

わさっき RSSフィード

2008年06月08日

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

研究室のゼミ発表で,「オーダーのことはよく分かっていませんが…」という前置きで計算量の見積もりをしているものを,昨年,今年と見かけました.

この日記が役に立つか,余計な御世話になるか分かっていませんが,ここに整理を試みてみました.

1. ビッグ・オー記法

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

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

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

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

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

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

例えば,2n^2+5n+3=O(n^2)となります.

また,10000n^{10}+2^n=O(2^n)です.どんな多項式関数よりも,指数関数のほうが,nを十分大きくすれば*3,大きい値になるためです.

次数については,主要なものを覚えましょう.

定数<¥log nnn¥log nn^2n^32^n3^nn!

それぞれに「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重ループ」というものではありません.疎な行列の計算では,それに応じた処理を書くほうが,効率が良くなります.

リンク元