アルゴリズム解析と計算量クラス

アルゴリズム解析は、入力に対するアルゴリズムのリソース要件がどのように増大するかを明らかにします。実装の詳細、ハードウェア、代表的なワークロードによって支配的なコストが見えにくくなる前に、設計上の意思決定を支援します。適切な解析では、入力サイズを特定し、対象とするリソースを定義し、上界を導出する前にコストモデルを明示します。

コストの定義 #

入力を表すサイズパラメーターを選択します。配列アルゴリズムでは \(n\) を使うことが多い一方、グラフアルゴリズムでは頂点 \(V\) と辺 \(E\) の両方が必要です。また、比較回数、メモリ消費量、ディスク I/O、ネットワーク往復回数、または定義したマシンモデルにおける経過時間など、対象とするリソースも明示します。

RAM モデルでは、ワードサイズの値に対する算術演算、比較、インデックス参照、ポインター操作を定数時間の操作として扱います。この仮定により、RAM モデルはメモリ内アルゴリズムに適しています。一方、外部メモリアルゴリズムでは、ランダムなディスクアクセスには定数コストがないため、ブロック転送を数える必要があります。

漸近記法 #

漸近記法は、入力が増大したときの非負のコスト関数を比較します。定数係数と低位項は、成長クラスを変えないため省略します。

\(f(n) \in O(g(n))\) とは、\(f(n) \leq c g(n)\) がすべての \(n \geq n_0\) で成り立つような定数 \(c > 0\) と \(n_0\) が存在することです。Big O は漸近的な上界を与えます。
\(f(n) \in \Omega(g(n))\) とは、\(g(n) \in O(f(n))\) であることです。Big Omega は漸近的な下界を与えます。
\(f(n) \in \Theta(g(n))\) とは、両方の関係が成り立つことです。Big Theta は漸近的にタイトな境界を与えます。

たとえば、\(3n^2 + 10n + 4\) は \(\Theta(n^2)\) です。二分探索はソート済み配列に対して \(O(\log n)\) 回の比較を行います。一方、隣接リストで表現されたグラフの幅優先探索は \(\Theta(V + E)\) 時間かかります。測定対象のリソースを伴わない境界は誤解を招く可能性があります。比較ベースのソートは \(O(n \log n)\) 回の比較で済んでも、補助メモリとして \(O(n)\) を必要とする場合があります。

反復アルゴリズムの解析 #

各ループが実行する処理量を数え、すべての反復について合計します。連続するループのコストは加算します。一方、一方のループのすべての反復ごとに他方のループのすべての反復が実行される場合に限り、ネストしたループのコストを乗算します。

cpp

#include <cstddef>
#include <vector>

std::size_t lower_bound_index(const std::vector<int>& values, int target) {
    std::size_t first = 0;
    std::size_t last = values.size();

    while (first < last) {
        const std::size_t middle = first + (last - first) / 2;
        if (values[middle] < target) {
            first = middle + 1;
        } else {
            last = middle;
        }
    }
    return first;
}

探索区間は各反復で少なくとも半分になります。したがって、実行時間は \(O(\log n)\) であり、反復実装が使用する補助領域は \(O(1)\) です。ループ境界が前のループ変数に依存する場合は、総和を用いる必要があります。たとえば、\(\sum_{i=1}^{n} i = \Theta(n^2)\) です。

漸化式と分割統治 #

再帰アルゴリズムでは、漸化式が現れることがよくあります。マージソートは入力を二つの半分に分割し、線形時間でマージするため、次のようになります。

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

再帰は \(\log_2 n\) 個のレベルを持ち、各レベルで \(\Theta(n)\) の処理を行います。したがって、マージソートの実行時間は \(\Theta(n \log n)\) です。再帰木を使うと、この構造を直接確認できます。\(T(n) = aT(n / b) + f(n)\) の形の漸化式では、マスター定理が \(f(n)\) と \(n^{\log_b a}\) を比較して結果を分類します。マスター定理の前提条件を満たさない場合は、再帰木または代入法による証明を使用します。

最悪時、期待値、償却コスト #

最悪時解析は、特定のサイズを持つすべての入力を上から評価します。最悪の入力がまれであっても、信頼できる容量上限を提供します。平均時解析には明示的な入力分布が必要です。そのような分布がない場合、境界を「平均」と呼んでも数学的な意味はありません。

期待値解析は、確率化アルゴリズムを対象とします。ピボット選択が敵対的な順序を避ける場合、ランダム化クイックソートの期待実行時間は \(\Theta(n \log n)\) です。ただし、特定の実行が \(\Theta(n^2)\) になる可能性はあります。

償却解析は、入力分布を仮定せずに、一連の操作を評価します。幾何学的に容量を拡大する std::vector への追加では、まれに再割り当てと \(\Theta(n)\) 個の要素のコピーが発生します。しかし、各要素がコピーされる回数は有限回に抑えられます。したがって、追加操作の列全体では、1 回の追加あたりの償却時間は \(O(1)\) です。集合的手法、会計法、ポテンシャル法は、このような境界を証明する同値な方法です。

判定問題と NP 完全性 #

判定問題は yes または no の答えを持ちます。多項式時間還元がそれらの答えを保存するため、計算量クラスは判定問題上で定義されます。

言語が P に属するとは、決定性マシンが多項式時間でそれを判定できることです。言語が NP に属するとは、すべての yes インスタンスが、決定性マシンによって多項式時間で検証できる証明書を持つことです。したがって、\(P \subseteq NP\) です。

すべての NP の問題から多項式時間還元が存在する問題は NP 困難です。NP 困難であり、かつ NP に属する問題は NP 完全です。NP 完全性の証明には、次のものが必要です。

NP への帰属を示す多項式時間検証器。
既知の NP 完全問題からの多項式時間還元。

\(P = NP\) かどうかという問題は、依然として未解決です。NP 完全性は、実用的なインスタンスが解けないことを意味しません。問題構造、パラメーターの上限、近似アルゴリズム、ヒューリスティクスによって、特定のインスタンスを扱いやすくできる場合があります。