📐

O記法の「=」って実は正しくない？！

に公開
math
アルゴリズム
計算量
idea

はじめに

アルゴリズムの計算量を表すとき、こんな表記を見たことがあるはずです。

4n \log n + \log n = O(n \log n)

この「=」、実は数学的には正しくありません。

「え、どういうこと？」と思った方、ご安心ください。この記事では、この「=」の正体と、なぜこの書き方が許されているのかを解説します。

O記法の「=」への疑問

O 記法の正式な定義

まず、O 記法が何を表しているのかを確認しましょう。

O(n^2) と書いたとき、これは関数の集合を意味します。

具体的には、「n が十分大きくなったとき、n^2 の定数倍以下に収まる関数」をすべて集めたものです。

例えば、以下の関数はすべて O(n^2) に含まれます。

  • n^2
  • 2n^2 + 3n + 1
  • n（n^2 より小さいので当然OK）
  • 1000（定数も含まれる）

本当は「\in」で書くべき

O(g(n)) は集合なので、数学的には \in（要素記号）を使うべきです。

4n^2 + 100n + 500 \in O(n^2)

しかし、実際の教科書や論文では、ほとんどの場合こう書かれています。

4n^2 + 100n + 500 = O(n^2)

なぜでしょうか？

「適切な乱用」という文化

実は、この「=」の使い方は記法の乱用（abuse of notation）として広く認識されています。

「乱用」と聞くとネガティブに聞こえますが、数学の世界では意味を正しく理解した上での省略や簡略化は許容されています。むしろ推奨されることもあります。

「=」を使う利点

では、具体的にどんな利点があるのでしょうか？

利点1：式変形が自然にできる

再帰的なアルゴリズムの計算量は、漸化式で表されることがあります。

例えばマージソートの計算量を T(n) とすると：

T(n) = 2T(n/2) + \Theta(n)

ここで \Theta(n) は「マージにかかる時間」を表しています。正確な係数は重要ではないので、\Theta(n) で「詳細を隠して」いるのです。

「\in」を使うと冗長になりますが、「=」ならシンプルに書けます。

利点2：連鎖的な式変形ができる

「=」を使えば、次のように式を連鎖させることができます。

\begin{aligned} 2n^2 + 3n + 1 &= 2n^2 + \Theta(n) \\ &= \Theta(n^2) \end{aligned}

「\in」だとこのような連鎖的な変形が書きにくくなります。

等号の解釈ルール

ただし、この「=」の解釈にはルールがあります。

ルール1：右辺に単独で現れる場合

4n^2 + 100n + 500 = O(n^2)

O 記法が右辺に単独で現れる場合、「=」は「\in」と同じ意味になります。

ルール2：式の中に現れる場合

2n^2 + 3n + 1 = 2n^2 + \Theta(n)

式の一部として漸近記法が現れる場合、それは「何らかの具体的な関数」を表します。

上の例では、\Theta(n) は「3n + 1」を指しています。

ルール3：左辺に現れる場合

2n^2 + \Theta(n) = \Theta(n^2)

左辺に漸近記法が現れる場合は、「どんな関数を当てはめても等式が成り立つ」 という意味です。

例えば：

  • \Theta(n) に 3n を当てはめると → 2n^2 + 3n → \Theta(n^2) に属する ✓
  • \Theta(n) に 100n + 5 を当てはめると → 2n^2 + 100n + 5 → \Theta(n^2) に属する ✓

まとめ

  • O(g(n)) は関数の集合として定義されている
  • 厳密には f(n) \in O(g(n)) と書くべき
  • しかし慣習的に f(n) = O(g(n)) と書く（「適切な乱用」）
  • この乱用には明確な解釈ルールがある
  • 利点：式変形が自然にでき、余計な詳細を気にせず済む

O 記法における「=」は、数学的な等号ではありません。しかし、その意味を正しく理解していれば、余計な詳細を気にせず議論を進められる便利なツールになります。

参考文献

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Fourth Edition. MIT Press, 2022.

Discussion