1 オーダー記法の概要
1.1 目的と直感
1.1.1 成長率を比較する考え方
オーダー記法は、ある量が「入力サイズ」や「変数が十分大きいとき」にどの程度増えるかを、支配的な成分に注目して比較するための記号体系である。計算量や誤差、規模の増加などを扱う際、「どの項が限界で支配するか」を捉えることで、異なる式でも同じ増え方をするかを簡潔に述べられる。
たとえば、同じ多項式でも係数や定数項の違いは最終的な成長の速さに影響しにくい。そこで「十分大きい領域では、関数の増加がほぼ同じ種類の速さになる」という観点で分類する。
1.1.2 定数倍・低次の項を無視する理由
オーダー記法が定数倍や低次の項を無視する理由は、(1) それらが極限的には支配的でなくなりやすいこと、(2) 実装上の定数差は環境依存で変動しうること、(3) 設計・解析の段階で重要なのは漸近的な傾向であること、の三点にまとめられる。
さらに、アルゴリズム比較では「ある入力領域を超えると必ずどちらが増え方として有利か」という構図がしばしば本質となる。定数倍や初期条件を細部まで追うより、支配的成長に基づく判断のほうが一般性を保てる。
1.2 計算複雑性との関係
1.2.1 漸近解析における位置づけ
計算複雑性理論では、計算時間やメモリ使用量を入力サイズの関数として扱い、その成長を分類する。オーダー記法は、その分類を可能にする共通語として機能する。たとえば「多項式時間で解ける」「指数的に増える」といった境界は、厳密な係数よりも漸近の形に依存するため、オーダー記法が適している。
また、厳密な等式や数値の一致ではなく、「上界」「下界」「同等性」といった関係で議論を進められる点が重要である。
1.2.2 アルゴリズム評価での利用
実務的には、アルゴリズムの設計段階で計算量の式を導き、オーダー記法でまとめることで比較可能になる。たとえば同じ機能を達成する複数手法があっても、支配的成分が異なれば大規模入力での挙動が変わりうる。
加えて、教科書的な評価（ループ回数、漸化式、再帰の深さなど）から得られる式はしばしば複雑であるが、オーダー記法へ落とし込むことで要点が抽出される。
1.3 記号の種類
1.3.1 上界・下界・同等性の使い分け
オーダー記法は複数の記号で役割分担される。上界を表すのはオー記法であり、ある範囲以降で「高々これくらい」の増加を保証する。下界を表すのがオメガ記法で、「少なくともこれくらい」の増加を示す。シータ記法はオーとオメガの両方を満たす形で、「ほぼ同じ種類の速さで増える」ことを表す。
解析の目的により、上界だけを示せば足りる場合、性能の保証として下界が必要な場合、あるいは最適性を主張したい場合などで適切な記号を選ぶ。
2 基本定義（形式的な表現）
2.1 オー記法（上界）
2.1.1 数学的定義の要点
関数 \(f(n)\) が \(O(g(n))\) であるとは、ある正の定数 \(c\) と閾値 \(n_0\) が存在して、すべての \(n \ge n_0\) に対して \[ f(n) \le c\,g(n) \] が成り立つことを意味する。ここで \(n\) は入力サイズ、\(g(n)\) は比較対象となる成長の基準である。
要点は、(1) 係数は任意の正の定数として吸収され、(2) 小さな \(n\) でのズレは閾値 \(n_0\) によって無視でき、(3) 大きな領域での優越関係のみが問題になる点にある。
2.1.1.1 係数と閾値の役割
定数 \(c\) は「どれくらい上振れしてよいか」を表し、定義の中で自由に選べる。閾値 \(n_0\) は「十分大きいところから議論する」という意味を与える。したがって、有限個の例外を許す形になり、漸近的性質に集中できる。
2.1.2 代表的な例
たとえば \(f(n)=3n^2+5n+1\) は \(O(n^2)\) である。理由は、\(n\) が大きいとき \(3n^2\) が支配的になり、残りの項は \(n^2\) に吸収されるからである。具体的には十分大きい \(n\) で \[ 3n^2+5n+1 \le c n^2 \] となる \(c\) を選べる。
また、指数関数 \(2^n\) に対して多項式 \(n^k\) は \(O(2^n)\) となる一方で、逆に \(2^n\) が \(O(n^k)\) になることはない。これは増加の階層が異なることを示す。
2.2 オメガ記法（下界）
2.2.1 数学的定義の要点
関数 \(f(n)\) が \(\Omega(g(n))\) であるとは、ある正の定数 \(c\) と閾値 \(n_0\) が存在して、すべての \(n \ge n_0\) に対して \[ f(n) \ge c\,g(n) \] が成り立つことをいう。上界と対になる概念であり、「少なくともこれくらいの成長」を主張する。
2.2.2 代表的な例
\(f(n)=n\log n\) は \(\Omega(n\log n)\) であるのは明らかで、さらに \(f(n)=n\log n\) は \(\Omega(n)\) でもある。対数は成長が遅いものの、正の範囲では消えず、線形式より速い増加をもつ。
同様に、指数関数 \(2^n\) は \( \Omega(2^n)\) であるだけでなく、たとえば \(\Omega(3^n)\) ではない（\(2^n\) は \(3^n\) より遅い成長のため）という関係が成立する。
2.3 シータ記法（厳密な増加率）
2.3.1 数学的定義の要点
関数 \(f(n)\) が \(\Theta(g(n))\) であるとは、ある正の定数 \(c_1,c_2\) と閾値 \(n_0\) が存在して、すべての \(n \ge n_0\) に対し \[ c_1 g(n) \le f(n) \le c_2 g(n) \] が成り立つことを意味する。上下双方の評価により、支配的な増加の種類が一致することを表す。
2.3.2 オー・オメガとの関係
シータ記法はオーとオメガの両方を含意する。すなわち \[ f(n) \in \Theta(g(n)) \iff (f(n) \in O(g(n)) \text{ かつ } f(n) \in \Omega(g(n))) \] が成り立つ。上界だけでは性能の上振れ可能性を残すが、シータなら同程度の成長が両側から保証される。
3 性質と計算法則
3.1 漸近変換の基本
3.1.1 多項式同士の比較
多項式の比較では次数が中心となる。たとえば \(n^k\) と \(n^m\) を比べると、\(k>m\) なら \(n^k\) は \(O(n^k)\) である一方、\(O(n^m)\) にはならない。より一般には、次数が大きい側が漸近的に優越する。
また、低次の項を足し引きしても次数が変わらない限りオーダーは同じままである。たとえば \(n^3+5n^2+7\) は \(\Theta(n^3)\) にまとまる。
3.1.2 対数・指数の比較
対数と多項式の関係では、\( \log n\) は任意の正の次数の多項式より遅いが、定数よりは速い。よって \(n^k\) のような多項式は、\((\log n)^m\) より速く増える。
指数同士では、底の違いにより成長順位が決まる。一般に \(a> b>1\) のとき \(a^n\) は \(b^n\) より速く、漸近的には一方が他方を定数倍で抑えられない。指数と対数が混在する場合も、支配的成分を特定することでオーダーが決まる。
3.2 代表的な合成操作
3.2.1 和・差のオーダー
和については、支配的な項が結果を決めるのが基本原則である。たとえば \(f(n)=O(g(n))\) と \(h(n)=O(k(n))\) のとき、\(f(n)+h(n)\) は概ね大きい方の成長に支配され、しばしば \[ f(n)+h(n)=O(\max\{g(n),k(n)\}) \] の形でまとめられる。
差についても同様で、互いが同程度に大きいと打ち消しが起こりうるため注意が要る。ただし一般的な評価では、通常は大きい方が残るという見積もりが使われる。
3.2.2 積・商のオーダー
積では成長の速さが掛け算で合成され、上界・下界がそれぞれ対応する形で扱える。代表的には、\(f(n)=O(g(n))\) かつ \(h(n)=O(k(n))\) なら \[ f(n)h(n)=O(g(n)k(n)) \] と見積もれる。
商では割り算により増加が抑えられることがあるが、分母がゼロに近づかないことや正値性などの前提が重要になる。漸近では、分母の支配的成長が分子をどれだけ上回るか、あるいは下回るかでオーダーが決まる。
3.3 上界・下界の推論
3.3.1 連鎖的な評価
複数の不等式を段階的に適用して最終的な評価を得るのが典型である。たとえば、ある式をいったん \(O\) によって上から抑え、さらに別の部分に対しても上界を適用していくと、全体としての上界が合成される。
このとき鍵になるのは、「どこで支配的な項が現れるか」を追跡することで、途中の見積もりが粗すぎると最終結果が過大になりやすい。
3.3.2 不等式を使った見積もり
オーダー判定は、しばしば単純な不等式によって行われる。例えば多項式はある次数以上では他の項を上から抑えられる、対数は指数に対して抑え込める、といった形で境界が作られる。
また、階層（多項式、準指数、指数など）の性質を使えば、直接比較が可能になる。反復回数や和の形が出たときも、積分評価や一般化された比較法を用いて上界・下界を構成できる。
4 計算例と応用
4.1 関数のオーダー判定
4.1.1 多項式・対数の例
\(f(n)=n^2\log n+3n\) は \(\Theta(n^2\log n)\) と整理できる。理由は、\(n^2\log n\) が \(n\) より十分速く増えるため、和の結果は支配項で決まるからである。
一方、\((\log n)^3 + 5\log n\) は \(\Theta((\log n)^3)\) となる。対数同士の比較ではべきの次数が支配的になり、低いべきは高いべきに吸収される。
4.1.2 階乗・冪・指数の例
階乗 \(n!\) は指数 \(c^n\) や冪 \(n^k\) より圧倒的に速く増える。したがって \(n!\) は \(\Omega(c^n)\) かつ \(\Omega(n^k)\) のような下界主張が成立しやすい（対象となる \(c>1\), \(k\) に応じて具体化する）。
冪 \(n^k\) は指数 \(a^n\) に比べれば遅い。よって \(n^k=O(a^n)\) は成り立ち、一般に冪が指数を \(O\) で抑えることはできない。
指数同士では \(2^n\) と \(3^n\) の関係が例になる。前者は後者に対して \(\,o(3^n)\) 的な振る舞いをし、上界も下界も同じオーダーにはならない。
4.2 アルゴリズムの計算量への適用
4.2.1 典型的なループ構造
二重ループがそれぞれ \(n\) 回ずつ回るなら、基本操作はおおむね \(n^2\) 回となり、計算量は \(\Theta(n^2)\) に対応することが多い。ループの入れ子の深さが増えるほど、支配的な次数が上がる。
一方、外側が \(n\)、内側が \(\log n\) 回のような場合、合計は \(n\log n\) にまとまる。ループの停止条件が対数のような形になると、オーダーが混在して見積もりが変わる。
4.2.2 再帰の増加率（概要）
再帰アルゴリズムでは、入力をいくつに分け、それぞれに同じ処理を施し、さらに分割・結合のコストがどれだけかを組み合わせて増加率を決める。典型的には「入力サイズを一定割合で減らしつつ、分岐数が一定」の形が多く、その場合はオーダーが既知のパターンに分類できることがある。
具体計算では漸化式を立て、支配的な項を特定して \(\Theta\) や \(O\) を導く。詳細な導出は手法（漸化式の変形、木構造の見積もりなど）に依存するが、最終的には「深さ」「各段の作業量」「総和」が決め手となる。
4.3 よくある誤解と注意点
4.3.1 定数を無視しすぎる落とし穴
定数や係数は無視されがちだが、常に単純に削ってよいわけではない。特に、計算対象が小さい領域では定数が支配的なこともあり、数値上の優劣と漸近的優劣が一致しない場合がある。
また、誤差評価では定数倍ではなく加算による影響が残ることがあり、単純な和の整理ができない構造もある。オーダーの評価は「十分大きい \(n\)」という条件を前提にしているため、適用範囲を意識する必要がある。
4.3.2 増加の向きの取り違え
上界と下界を取り違えると、主張の意味が反転してしまう。たとえば「常に高々 \(g(n)\)」は \(O(g(n))\) であり、「少なくとも \(g(n)\)」は \(\Omega(g(n))\) である。混同すると、性能保証の形が誤って伝わる。
さらに、同じ記号でも「どの変数に対する増加か」を取り違えることがある。入力サイズが \(n\) なのか、処理対象の別の尺度が \(m\) なのかを明確にしないと、正しい比較にならない。