1 計算量の基本概念
計算量とは、アルゴリズムが入力の大きさに応じて消費する計算資源の増え方を評価する概念である。通常は計算時間と記憶使用量を中心に扱い、入力が大きくなるにつれて必要資源がどの程度増大するかを整理することで、異なる手法の効率を比較しやすくする。
1.1 計算量が測る対象
計算量は「実行に必要な資源」を対象とするが、評価の主眼は入力サイズの増加に伴う成長率に置かれる。具体的には時間と空間（記憶容量）を別々に定義し、必要に応じて同時に検討する。
1.1.1 計算時間
計算時間は、アルゴリズムが入力を処理する際に実行される基本操作の回数や、モデル上の経過時間として表現される。一般に、入力サイズの増加に対する操作回数の増加傾向が評価対象となる。
1.1.1.1 漸近的な時間評価（最良・平均・最悪）
漸近的な時間評価では、入力の条件や入力の分布に応じて時間の上界・下界を整理する。最良の場合は最も都合のよい入力に対する挙動、平均の場合は入力がある分布から選ばれるときの期待的な挙動、最悪の場合は最も処理が重い入力に対する挙動をそれぞれ示す。これらにより、状況が異なるときの性能の見通しを得られる。
1.1.2 記憶容量
記憶容量は、計算中に保持する情報量の増え方を表す。配列や連想配列などの作業領域、再帰呼び出しに伴うスタック、補助変数のような一時的な領域が対象に含まれ得る。時間と同様に、入力サイズが増えたときに必要空間がどの程度増えるかが重要になる。
1.1.2.1 補助記憶と入出力の扱い
分析では、計算に直接必要な補助記憶を中心に扱う一方で、入出力の影響は取り扱いが分かれる。たとえば入力データの読み込みや出力の書き込みは、モデルや問題設定によって支配要因になり得るため、時間・空間のどちらにどの程度含めるかを明示することが望ましい。理論分析では、入出力を別枠とし処理時間から切り離す流儀もある。
1.2 入力サイズとパラメータ
計算量の評価は「何を入力サイズとみなすか」に依存する。入力の表現形式や、問題のパラメータの定義が異なると、同じアルゴリズムでも計算量の見え方が変わる。
1.1.2 入力の表現（エンコード）
入力を符号化して長さとして扱うとき、エンコードの選び方が重要になる。整数を固定長で表すのか、可変長で表すのか、文字列や多倍長数をどう長さに対応させるかで、サイズ指標が変わる。一般に、ビット長を基準にすることで表現差の影響を抑えやすい。
1.2.2 サイズ指標の選び方
多くの理論解析では、入力長（ビット数）や、問題の自然なパラメータ（頂点数、要素数、長さなど）をサイズとして用いる。どちらを選ぶべきかは、問題の本質とエンコード規則により決まる。サイズの定義を適切に揃えることで、比較の公平性が高まる。
1.3 漸近的記法
漸近的記法は、入力サイズが十分大きいときの成長率を表すための数学的表現である。定数倍や低次の項をならし、支配的な増加傾向に焦点を当てる。
1.3.1 O記法
O記法は上界を表す。関数 f(n) が O(g(n)) であるとは、ある定数 c と閾値 n0 が存在して、n≥n0 のとき f(n)≤c·g(n) が成り立つことを意味する。アルゴリズムの「高々この程度」という保証に対応する。
1.3.2 Ω記法
Ω記法は下界を表す。f(n) が Ω(g(n)) であるとは、十分大きい n で f(n)≥c·g(n) が成り立つような定数 c を持つことを意味する。これは「少なくともこの程度は必要」という見積もりに相当する。
1.3.3 Θ記法
Θ記法は上下界が一致する成長率を表す。f(n) が Θ(g(n)) であるとは、f(n) が O(g(n)) かつ Ω(g(n)) の両方を満たすことを指す。支配的な次数が確定している場合に用いられる。
2 アルゴリズム評価の枠組み
アルゴリズム評価は、見積もりの手順と計算モデルを明確にすることで再現性が高まる。解析の目的に応じて、操作の数え方や仮定する計算資源の扱いを整える。
2.1 計算量の算出手順
計算量の算出は、アルゴリズムの構造を分解し、支配的な増加要因を特定する作業として進められる。最終的には漸近記法で成長率を表す。
2.1.1 擬似コードからの見積もり
擬似コードから時間や空間を見積もるときは、基本操作、制御構造、繰り返しの回数に着目する。分岐がある場合は条件によって回数が変わるため、最良・平均・最悪のどれを見ているかを先に決めると整理しやすい。
2.1.1.1 ループ・再帰の回数評価
ループでは反復回数が入力サイズとどう関係するかを数える。たとえば二重ループなら外側の回数に内側の回数が掛かるため、積として増えることが多い。再帰では呼び出し回数の増え方と、各段での処理量を合わせて考える必要がある。
2.1.2 漸化式の扱い
再帰的定義は漸化式として表し、解を求めることで成長率を導く。典型的には、問題サイズがどのように縮むか、同時にどれだけの部分問題が生成されるかを式に反映する。解法には、置換法や既知のパターンへの照合などが使われる。
2.1.3 具体例による手計算
具体例の手計算では、支配的項を見つけることが中心となる。単純なループなら次数を直接読み取れるが、複合的な処理では最も増え方が大きい部分が全体を支配することが多い。この考え方に基づき、無視できる低次の寄与を整理して記法へ落とし込む。
2.2 実行時間の理論モデル
理論的な計算量は、どのような計算モデルに基づくかで解釈が変わる。モデルは「基本操作とは何か」「資源の測り方」を定める枠組みである。
2.2.1 RAMモデル
RAMモデルでは、レジスタ操作や算術演算などを一定時間の基本操作として扱い、メモリアクセスをほぼ同等のコストとして近似する。これにより、実装言語やハードウェアの細部を一定程度捨象して解析が可能になる。
2.2.2 一様性と計算資源の仮定
一様性とは、入力サイズごとに機械や回路の設計が一貫した規則に従うかどうかの考え方であり、計算モデルの厳密化に関わる。加えて、乱択の有無、メモリの扱い、演算精度などの仮定が結果の解釈に影響する。したがって、分析の前提を明確にすることが重要である。
2.3 ケース別の計算量
計算量は状況によって異なるため、典型的な入力条件ごとに整理する。最良・平均・最悪という区分は、解析の中心的な枠組みとして用いられる。
2.3.1 最良時計算量
最良時計算量は、入力がアルゴリズムにとって最も都合のよいときに要する資源を示す。枝刈りが大きい探索や、条件分岐で早期終了する手続では、この値が小さくなりやすい。一方で、実データが最良に偏るとは限らない点に注意が必要である。
2.3.2 平均時計算量
平均時計算量は、入力が確率分布に従って与えられると仮定したときの期待的な資源消費を表す。分布仮定が変わると値も変わるため、採用する確率モデルの妥当性が解釈の鍵となる。実務では、経験的な分布や観測に基づいて判断することが多い。
2.3.3 最悪時計算量
最悪時計算量は、最も処理が重くなる入力に対する資源を表す。アルゴリズムの頑健性を評価する目的で用いられることが多く、保障としての意味が強い。特に安全性や応答時間の上限制約がある場面では重要度が高い。
3 よく現れる計算量クラス
計算量の成長率には典型的なパターンがあり、これらは「クラス」として分類される。代表例を把握することで、解析結果を直感的に理解しやすくなる。
3.1 多項式時間
多項式時間は、入力サイズの冪で増える計算量の総称である。次数が高いほど増加は急になるが、指数的成長に比べると現実的に扱える範囲が広いとされる。
3.1.1 平易な多項式（例：一次・二次）
一次の例は線形的な増加に対応し、二次の例は二重の組み合わせが現れるような状況で見られることが多い。一般に、多項式次数はアルゴリズム構造の階層（ループの入れ子や再帰木の広がり）と関係する。
3.1.2 多項式の係数と実務上の注意
多項式時間は「次数」だけで評価しがちだが、係数や定数項は実行時間に影響する。特に入力が中規模のときは、漸近的には同程度に見える手法でも実際の速度差が大きくなる場合がある。理論上の優劣と実装上の選択を切り分けて判断する必要がある。
3.2 超多項式・指数関数
超多項式は、多項式よりも速く増える成長を指すことが多い。解析上は指数関数や階乗のような形が代表的で、入力が増えると資源要求が急激に膨らむ。
3.2.1 指数時間（例：2^n）
指数時間は、入力サイズに対して指数的に操作回数が増える状況を表す。分岐探索や全探索のように可能性を列挙する構造で現れやすい。nが大きいと実行は困難になりやすく、近似や枝刈り、ヒューリスティクスが検討対象になる。
3.2.2 階乗時間（例：n!）
階乗時間は、順列の数の増え方に近い成長を示す。固定順序の列挙ではなく、順序の違いまで含めた可能性を列挙する場面で見られることがある。指数時間よりさらに急で、入力の増加に対する現実性が急速に失われる。
3.3 対数・準線形
対数や準線形は、多項式の中でも低い増加傾向としてよく登場する。高速な探索や整列の一部で頻出する。
3.3.1 対数時間（例：log n）
対数時間は、問題サイズを段階的に縮める手続や、探索空間が毎回一定割合で絞り込まれる状況で生じる。たとえば二分探索のような枠組みが典型例である。入力が増えても必要操作はゆっくり増える。
3.3.2 準線形（例：n log n）
準線形は n に対数因子が掛かった形で、効率のよい整列や分割統治型アルゴリズムの解析でよく現れる。線形よりは大きいが、指数的な増加とは大きく隔たっているため、実務でも広く採用されることが多い。
3.4 定数・線形
定数時間と線形時間は、最も素朴な成長パターンとして理解されることが多い。入力増加の影響が軽い場合の指標となる。
3.4.1 定数時間（O(1)）
定数時間は入力サイズが増えても処理量が増えない、あるいは解析上無視できることを意味する。配列の先頭参照や、固定長の計算のように扱える場合に成立しやすい。ただし実装の細部で定数が大きくなることはあり得る。
3.4.2 線形時間（O(n)）
線形時間は、入力の要素数に比例して処理が増える状況を示す。全要素を一度走査する処理で現れやすい。必要性のある検査を単に繰り返すだけで終わる場合は、改善余地が限定されることもある。
4 分析の応用と限界
計算量の知見は設計や評価に活用できるが、現実の制約や測定の難しさから、理論結果だけでは判断できない場合もある。
4.1 計算量改善の設計指針
改善の方針は、問題構造に合ったアルゴリズム設計を選ぶことに尽きる。よく使われる設計パターンは、計算量の形を変える力を持つ。
4.1.1 分割統治
分割統治は、問題を小さな部分に分けて解き、結果を合成する考え方である。部分問題の解法と結合コストのバランスにより、準線形や対数的挙動が実現されることがある。再帰深さと統合処理の設計が要点になる。
4.1.2 動的計画法
動的計画法は、部分問題の解を保存し、重複計算を抑える手法である。状態の設計と遷移の定義が適切であれば、指数的に膨らむ探索を多項式へ抑え込めることがある。ただし状態数が増えると別のコストが支配的になる。
4.1.3 貪欲法
貪欲法は、局所的に最も良い選択を積み重ねることで全体を目指す。計算量は選択操作と更新回数に左右され、データ構造の効率と相性が良い場合は高速化につながる。ただし最適性が保証される条件を満たすかの確認が必要である。
4.1.4 データ構造による高速化
データ構造の選択は、同じ手続でも計算量を変える要因になり得る。検索・挿入・更新のコストが変わることで、合計処理量が改善される。たとえば順序を保つ構造や、区間演算に特化した構造は、パターンに合えば劇的な差を生む。
4.2 下界と「これ以上速くできない」話
理論計算量では、アルゴリズム改善の限界を示す下界も重要になる。これにより、無駄な最適化を避け、焦点を移す判断ができる。
4.2.1 下界の考え方
下界は、どのアルゴリズムでも避けられない最小の計算量を議論する枠組みである。問題の性質や情報量、計算モデルの制約に基づき、特定の処理が必ず発生するという形で主張される。下界の種類によって強さや適用範囲が異なる。
4.2.2 計算量の不可避性の例
典型的な例として、入力から情報を得るために最低限必要な操作が存在する場合がある。たとえば比較に基づく並べ替えでは、比較回数に起因する下界が議論されることが多い。こうした状況では、定数倍の工夫よりも手続の枠組みを変える必要が出てくる。
4.3 実務での落とし穴
理論上の計算量と、実際の性能は一致しないことがある。性能評価では、測定方法やハードウェア特性も含めた考慮が求められる。
4.3.1 定数倍・メモリ効率
計算量が同じ次数でも、定数倍やメモリアクセスの形（局所性、キャッシュ効率）で速度差が出る。さらに、メモリ使用量が増えるとページングやガベージコレクションなどの副作用が現れ、理論的な空間評価と実際の体感が乖離しやすい。
4.3.2 入出力が支配する状況
大量のデータを読み書きする処理では、計算量より入出力が支配要因になることがある。理論モデルで入出力コストを無視した場合、性能見積もりが過小になる場合があるため、入出力のコストを別途評価するか、モデルに取り込むことが望ましい。
4.3.3 理論評価とベンチマークの差異
ベンチマークは現実条件を反映する一方で、入力分布や実装の細部、コンパイラ最適化などに影響される。理論解析は一般性を重視するため、特定環境での最適解と一致しないことがある。両者の差を理解したうえで、目的に合う判断基準を選ぶことが重要になる。