| 文責: | @ayato_p |
|---|
計算の資源 (メモリなど) を消費する速度は, プロセスによって大いに違う. この違いを記述する便利な方法の一つは, プロセスが入力が大きくなるにつれて必要とする資源を, 粗く見積もる 増加の程度 (order of growth) の考えを使うことである.
\(n\) を問題の大きさを表すパラメタ, \(R(n)\) を大きさ \(n\) の問題に対してプロセスが必要とする資源の量とする．前の例で言えば, \(n\) をそれに対して関数を計算しようとする数にしたが, 別のものにする可能性もある.
もし任意の十分に大きな \(n\) の値に対して, 整数 \(k_1\) と \(k_2\) が \(n\) に独立して存在し \(k_1f(n) \leq R(n) \leq k_2f(n)\) を満たすとき, \(R(n)\) は増加の次数 \(\Theta(f(n))\) を持ち \(R(n) = \Theta(f(n))\) と記述できる. 階乗計算の線形再帰的プロセスのステップ数は, 入力 n に比例して増加する. 従ってこのプロセスの必要とするステップ数は \(\Theta(n)\) で増加する. また, 必要な記憶域も \(\Theta(n)\) で増加した. 反復的階乗では, ステップ数はやはり \(\Theta(n)\) だが, 記憶域は \(\Theta(1)\), つまり定数となる. 木構造の Fibonacci 計算は \(\Theta(\phi^n)\) ステップと, \(\Theta(n)\) の記憶域を必要とする.
増加の次数はプロセスの行いについて概観的な説明を与える. 例えば \(n^2\) ステップ, \(1000n^2\) ステップ, \(3n^2+10n+17\) ステップを必要とするプロセスは全て増加の次数は \(\Theta(n^2)\) になる. 一方で増加の次数は問題のサイズを変更した場合にどの程度プロセスの挙動が変化するかを推測するのに実用的な指標です. \(\Theta(n)\) の線形プロセスに対しサイズを 2 倍にした場合, 概ね 2 倍のリソースを使用します. 指数関数的プロセスに対しては問題サイズを 1 増やす度, 定数因子をリソース使用率にかけることになります.