1 Θ記法の基本
1.1 定義と直感
1.1.1 上限と下限の同時成立
Θ記法は、成長率の比較において「同程度」を表す。関数の値が入力サイズに応じてどのように増えるかを、上限と下限の両面から挟み込む形で捉える点が特徴である。具体的には、ある基準となる関数 \(g(n)\) に対し、対象の関数 \(f(n)\) が十分大きい範囲で \(g(n)\) の定数倍の範囲内に収まるとき、ふたつの関係（上界と下界）が同時に成立していることを意味する。これにより、単に「増え方が速い」「遅い」といった片面的な評価ではなく、漸近的な振る舞いの強い一致を主張できる。
1.1.2 係数と「十分大きい」の意味
Θ記法で許容される誤差は、次数（成長のオーダー）に関するものであり、定数係数までは厳密に一致することを要求しない。上限側と下限側はどちらも「ある定数を用いれば到達できる」形で記述されるため、係数の違いは通常は問題にならない。一方で、「十分大きい \(n\)」という条件により、低い領域での振る舞いは無視できる。つまり、初期の \(n\) では不均衡に見えることがあっても、一定の閾値以降に同じ成長パターンへ落ち着くならΘとして扱える。
1.2 表記の例
1.2.1 多項式同士の比較
多項式の比較はΘ記法を理解するうえで典型的である。たとえば、次数が同じ多項式同士は同じΘクラスに入ることが多い。直観的には、支配的な項が同じ次数を持つため、\(n\) を大きくしていくと高次の成分が振る舞いを決めるからである。たとえ係数が異なっていても、定数倍の違いとして吸収されるため、上限と下限を同時に作れる範囲が存在すればΘが成立する。
1.2.2 対数・指数関数の比較
対数や指数は成長速度の階層が大きく異なるため、Θの比較では「どれが支配項か」を明確に意識する必要がある。対数同士は、底が異なっていても定数倍として扱え、漸近的には同じオーダーになることが多い。指数は指数の種類により急激に増加し、加えて多項式は指数に比べてはるかに遅い。このため、例えば「指数が多項式に対して必ず支配する」といった事実は、Θの枠組みで裏づけられることが多い。
2 Θ記法の形式的取り扱い
2.1 証明の基本手順
2.1.1 上界の示し方
2.1.1.1 定数・閾値の具体化
Θの証明では、まず上界側を示す。目的は、十分大きい \(n\) に対して \(f(n)\) が \(g(n)\) の定数倍以内に収まること、すなわち \(f(n) \le c\,g(n)\) を満たすような定数 \(c\) と閾値 \(n_0\) が存在することを示す点にある。証明ではしばしば、式変形によって \(f(n)\) をより単純な形へ落とし込み、既知の不等式や成長の優劣（例えば多項式が対数より速い等）を用いる。定数や閾値は一意ではないため、「存在」を示す形が中心となるが、実務では見通しをよくするために明示的に候補を構成することもある。
2.1.2 下界の示し方
下界側では逆向きの不等式、すなわち \(f(n) \ge c'\,g(n)\) を十分大きい \(n\) で成立させる必要がある。ここでは、\(f(n)\) が \(g(n)\) より「速くはない」ことではなく、「遅くない」ことを保証する。上界の作り方と同様に、適切な分解や支配項の特定を行い、必要な定数 \(c'\) と閾値 \(n_1\) を確保する。最終的には両方の不等式を同じ「十分大きい範囲」で同時に満たすよう、閾値を統合して扱う。
2.2 よくある証明パターン
2.2.1 不等式の組み立て
よく使われる方法のひとつは、不等式を複数段で組み立て、最終的に \(g(n)\) の定数倍に収める構造である。たとえば、分数や和・積の形が出た場合には、それぞれに対して上界／下界となる既知の評価を適用していく。特に和の評価では「最大の項が支配する」という事実が頻出する。積の評価では単調性や支配項の扱いが重要になり、対数や指数を含む場合は対数則・指数則といった恒等変形が証明を支える。
2.2.2 漸近的な単純化
漸近的な比較では、支配的でない項を無視してよいことが多い。Θの証明でも同様に、主要成分がどれかを見極め、残りはより簡単な関数で上から抑えるか下から押さえることがある。たとえば、多項式の中で最高次数の項を中心に考えると、他の項は十分大きい \(n\) で定数倍の枠に収まりやすい。単純化の段階では、単に「見た目」で捨てず、実際に不等式として整合する形で置き換えることが求められる。
3 ライブラリとしての計算量解析での位置づけ
3.1 O記法・o記法・Ω記法との関係
3.1.1 O記法との違い
O記法は上界のみを表す。つまり、\(f(n)\) が \(g(n)\) の定数倍を超えない、という片側の情報に対応する。Θ記法はこれに加えて下界も要求するため、同じ \(g(n)\) に対して「増加の速度が上からも下からも同じ程度である」ことを保証する点で強い。したがって、Oとして示せてもΘにならない例が存在し、下限が不足しているときに「成長率は遅い可能性が残る」状態になる。
3.1.2 Ω記法との違い
Ω記法は下界のみを表す。\(f(n)\) が \(g(n)\) の定数倍より遅くならないことを述べ、上からの拘束は提供しない。Θは両者を統合するため、Ωで下限だけが確立しても、上限が別の関数であり得る場合にはΘへ到達できない。計算量解析では、上界と下界を別々に扱うことで、アルゴリズムの可能性を狭めていくが、最終的に一致したときにΘが得られる。
3.2 アルゴリズム評価への応用
3.2.1 分析対象（時間・空間）
計算量解析でΘが使われる対象は主に実行時間と使用メモリ（空間）である。実行時間については、入力サイズに応じて基本操作が何回程度行われるかや、比較・演算などの回数をモデル化することで導く。空間については、補助配列や再帰の深さなど、必要なメモリ量が入力とどう関係するかを見積もる。Θによる評価は、片側だけでは分からない「規模の一致」を示せるため、性能の比較や設計判断に使いやすい。
3.2.2 代表的なアルゴリズムの分類
アルゴリズムの分類では、代表的な処理手順がどの成長率に落ち着くかを整理する。たとえば、単純な走査が支配する処理は線形に近いオーダーになりやすく、繰り返しを多重に含む構造では多項式的に増える傾向がある。対数的に縮む分割統治の形では対数が関係し、データ構造や再帰の条件によって定まる。Θが得られると、「この形のアルゴリズムは入力が大きくなるほど概ねこの程度に増える」という見通しが明確になる。
4 よくある誤解と実務上の注意
4.1 Θに見えるが実は異なる場合
4.1.1 片側しか成り立たない
誤解の典型は、上限か下限のどちらか一方しか示せていないのにΘとして結論することである。たとえば \(f(n)\) が \(g(n)\) より小さめに収まっていることを確認しただけでは、下限が別の関数に置き換わる余地が残る。反対に、下限を示しただけでも同様に不十分である。Θは二つの不等式が同じ基準関数に対して同時に成立する必要があるため、証明は必ず上下を別個に構築し、最後に閾値を統合して整合させるのが安全である。
4.1.2 定数倍の扱いに関する注意
定数係数は無視されることが多いが、すべてが無条件に扱えるわけではない。たとえば符号や前提条件（非負性など）によって、単純な定数倍の推論が成立しない場面がある。また、比較したい関数が \(n\) の変域やスケールで極端に小さい領域を含むと、「十分大きい」の条件の使い方が曖昧になり、誤った判断につながる。実務では、変数の範囲と、定数を置く根拠（どの不等式がどの範囲で成立するか）を明確にしておくことが重要である。
4.2 境界ケース（小さい n）
4.2.1 「十分大きい」が意味すること
Θ記法は漸近的概念であるため、少数の \(n\) における振る舞いは本質的に対象外になる。よって、ある小さい入力で上限・下限が破れて見えたとしても、閾値以降で整合するなら問題はない。ただし、実装の評価では「どれくらいの大きさからその近似が有効か」が体感に直結する。そのため、理論上の「十分大きい」を具体的に見積もる工夫（実験や保守的評価）が実務で役立つ。
4.2.2 実装での見積もりとの折り合い
理論上のΘは、定数倍をまとめてしまうため、実際の実行時間やメモリ使用量の差を完全には反映しない。たとえ同じΘに属していても、内部定数やデータ配置、分岐予測、メモリアクセスの局所性などで体感の差が生じる。したがって、実装段階ではΘで得た成長率の方向性をベースにしつつ、定数の要因も含めたベンチマークや微調整を行うのが現実的である。結果として、理論と実測のギャップを理解し、過度に単純化しない姿勢が求められる。