# 漸近記法 ## 定義 漸近記法(asymptotic notation)は、関数 $f,g$ の増大の程度(growth rate)を、定数因子や下位の項(low-order term)を無視して比較するための記法群である。関数の引数 $x$(あるいは $n$)が無限大に近づくときの挙動だけに着目する点が「漸近」の意味であり、アルゴリズムの実行時間のように、機種依存の定数や瑣末な下位項を無視して増大の程度だけを議論したい場面で使われる。以下の6種類がある。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] §13.4.3, §13.7) - **漸近的等号(asymptotic equality)** $f(x)\sim g(x)$: $\lim_{x\to\infty} f(x)/g(x)=1$ であることをいう。$f$ の最高次の項(leading term)が $g$ に一致することを表す。例えば $H_n \sim \ln(n)$ は、調和数の最高次の項が $\ln(n)$ であることを意味する。ただし $H_n \sim \ln(n)+c$($c$ は任意の定数)も成り立ってしまうため、2番目に大きい項まで正確に示したい場合は $\sim$ ではなく「$H_n - \ln(n) \to \gamma$」のような極限による表現を使う必要がある(定義13.4.2)。 - **Little o** $f(x)=o(g(x))$: $\lim_{x\to\infty} f(x)/g(x)=0$ であることをいう。$f$ が $g$ よりも真に(significantly)遅く増大することを表す(定義13.7.1)。例: 任意の非負の定数 $a<b$ について $x^a=o(x^b)$(補題13.7.2)。任意の $\epsilon>0$ について $\log x = o(x^\epsilon)$(補題13.7.3)。任意の $a>1,b\in\mathbb{R}$ について $x^b=o(a^x)$(系13.7.4)——すなわち、多項式は指数関数より真に遅い。 - **Big O** $f=O(g)$: 標準的な($\epsilon$-$\delta$風の)定義では、ある定数 $c\ge0$ と $x_0$ が存在し、すべての $x\ge x_0$ で $|f(x)|\le cg(x)$ が成り立つこと(定義13.7.9)。教科書は先に limsup を使う代替の定義を与える: $\limsup_{x\to\infty} |f(x)|/g(x) < \infty$(定義13.7.5)。limsup(最小上界の極限)を使うのは、$f(x)/g(x)$ が振動して通常の極限が存在しない場合(例えば3と5の間で振動する場合)にも $O$ を定義できるようにするためである。両定義は同値であり、極限が存在する場合は limsup と極限は一致する(補題13.7.6)。$f=o(g)$ または $f\sim g$ ならば $f=O(g)$ が従う(補題13.7.7)が、逆は成り立たない(例: $2x=O(x)$ だが $2x\not\sim x$ かつ $2x\ne o(x)$)。$f=o(g)$ ならば $g=O(f)$ は成り立たない(補題13.7.8)。$O$ は**上限のみ**を表す記法であり、下限の主張(「少なくともこれだけ増大する」)に $O$ を使うのは誤用である(下限には Ω を使う)。 - **Theta** $f=\Theta(g)$: $f=O(g)$ かつ $g=O(f)$ であることをいう(定義13.7.13)。「$f$ と $g$ は定数因子の範囲で等しい」ことを表し、上限と下限の両方を同時に主張する。例えば実行時間 $T(n)=10n^3-20n^2+1$ は $T(n)=\Theta(n^3)$ と書け、係数や下位項を無視して「立方のオーダーで増大する」ことだけを端的に表現できる。$\Theta(n^3)$ は $n$ が2倍になったとき実行時間がおおむね最大8倍になるという、スケーラビリティに関する情報を保持する。 - **big Omega** $f=\Omega(g)$: $g=O(f)$ であることと定義する(定義13.7.15)。下限を表す記法であり、「実行時間は少なくとも2次のオーダーである」と言いたければ $T(n)=\Omega(n^2)$ と書く。 - **little omega** $f=\omega(g)$: $g=o(f)$ であることと定義する(定義13.7.16)。他の記法ほど広く使われてはいない。 漸近記法は多くの直観的な誤用パターンを持つ。代表的な例として、底の異なる指数関数を定数倍の違いと誤認する誤り($4^x=O(2^x)$ は誤りで、実際には $4^x=(2^x)^2$ と2乗の関係にある)、定数 $O(1)$ を機械的に加算して和全体の $O$ を導く誤り($\sum_{i=1}^n i = O(1)+O(1)+\cdots+O(1)=O(n)$ という「証明」は誤りで、真の理由は各項 $i$ が $n$ に依存して変化する定数ではない点にある)、$f=O(g)$ の等号を対称に使って $O(g)=f$ と書き、そこから矛盾を導く誤り、掛け算・指数化などの演算が漸近関係を自動的に保存すると仮定する誤り(例えば $f\sim g$ から $3^f=\Theta(3^g)$ は一般に従わない)がある。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] §13.7.4, §13.7.5) ## 横断的知見 - 第21章(漸化式)は、分割統治漸化式の漸近解(Akra-Bazziの公式・マスター定理)をすべてΘ記法で表現し、第13章で定義された「fとgは定数因子の範囲で等しい」というΘの定義をそのまま踏襲する。これは本節の未解決の問いにあった「漸近記法とアルゴリズムの計算量解析との接続」への具体的な回答であり、Θがアルゴリズムの実行時間の増大クラス(多項式・対数・指数)を比較する道具として使われる典型例を与える。ただし第21章のマージソート(Θ(n log n))対ハノイの塔(Θ(2^n))の対比が使うΘは、増大のクラスそのもの(多項式か指数か)を区別する粗い粒度の主張であり、第13章§13.7.3が述べる「nが2倍になったとき実行時間がおおむね何倍になるか」という係数レベルの精度の主張とは異なる粒度で使われている。両者はΘという同じ記法の異なる使用文脈であり、文脈に応じてΘがどの精度の主張をしているかを読み分ける必要がある。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] §13.7.3, [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] §21.4, §21.5) ## 未解決の問い - $\Theta$ が「スケーラビリティの情報を保持する」という主張(§13.7.3)は、$T(n)\sim cn^3$ のように定数が単一に定まる場合にのみ2倍で正確に8倍になることが脚注8で断られている。$\Theta$ の定数幅 $[c,d]$ がスケーラビリティ予測の精度にどう影響するかは、他のアルゴリズム解析ソースで補強すべき論点。 - 第21章はΘ記法を漸化式の解の表現に使うが、計算複雑性理論の計算量クラス(P, NP等)そのものへの接続は依然として扱われていない。計算複雑性理論を扱う他ソースがingestされたら、この接続を補強する。 ## 関連 - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 21 Recurrences]] - 概念: [[和の近似]](積分限界法によって得られる近似式が漸近記法で表現される)、[[調和数]]($H_n \sim \ln(n)$ が漸近的等号の典型例)、[[分割統治]](Akra-Bazziの公式・マスター定理の解の表現にΘ記法を使う) ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 13 §13.4.3, §13.7. - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 21, §21.4〜§21.5.