這份筆記是關於函數量級的性質。
量級
定義 1：量級 (Order of Magnitude)
給定兩函數\(f(x)\)和\(g(x)\)。我們說\(f\)在無窮遠處比\(g\)高階，若 \[ \left|\frac{f(x)}{g(x)}\right|\to\infty\mbox{ when }x\to\infty \] 且我們說\(f\)在無窮遠處比\(g\)低階，若 \[ \left|\frac{f(x)}{g(x)}\right|\to 0\mbox{ when }x\to\infty \] 且我們說\(f\)在無窮遠處與\(g\)同階，若 \[ \left|\frac{f(x)}{g(x)}\right|\to c<\infty,c\neq 0\mbox{ when }x\to\infty \] 或對於夠大的\(x\)有 \[ 0<c_2\leq\left|\frac{f(x)}{g(x)}\right|\leq c_1<\infty \]
例 1-1：指數函數
給定\(a>1\)，考慮\(f(x)=a^x\), \(g(x)=x\)。
1. 普通估計：我們想說明\(f\)比\(g\)高階，即當\(x\to\infty\)時有\(\frac{a^x}{x}\to\infty\)。
證明：令 \[ \phi(x)=\log\frac{a^x}{x}=\log a^x-\log x=x\log a-\log x \] 而對於夠大的\(x\)，有\(\phi'(x)=\log a-\frac{1}{x}>0\)。故\(\phi\)在某個\(x\)之後嚴格遞增(這裡的性質5)。故有(詳見下面的第2.步) \[ \begin{aligned} &\lim_{x\to\infty}\log\frac{a^x}{x}=\infty\\ \Rightarrow&\lim_{x\to\infty}\frac{a^x}{x}=\infty \end{aligned} \] QED
2. 更好的估計：考慮\(\phi(x)-\phi(c)\)，其中\(c\)是使\(\log
a-\frac{1}{c}\geq\frac{1}{2}\log a\)的常數，則 \[
\begin{aligned}
\phi(x)-\phi(c)&=\int_c^x\phi'(t)dt\\
&\geq(x-c)\phi'(c)\mbox{ (☆)}\\
&\geq\frac{1}{2}(x-c)\log a
\end{aligned}
\] (☆)是因為\(\phi'(x)\)嚴格遞增。於是\(\phi(x)\)在\(x\)趨近無限大時也趨近無限大。
3. 更更好的估計：令\(\sqrt{a}=1+h=b\)，其中\(h>0\)。對於\(x\)，有\(n\in\mathbb{Z}\)使得\(n\leq x<n+1\)。則 \[
\sqrt{\frac{a^x}{x}}=\frac{b^x}{\sqrt{x}}\geq\frac{(1+h)^n}{\sqrt{x}}\geq\frac{1+nh}{\sqrt{x}}\geq\frac{1+nh}{\sqrt{n+1}}\geq\frac{nh}{\sqrt{2n}}=\frac{h}{\sqrt{2}}\sqrt{n}
\] 於是有 \[
\frac{a^x}{x}\geq\frac{h^2}{2}n\geq\frac{h^2}{4}x
\] 故\(x\to\infty\)時，\(\frac{a^x}{x}\to\infty\)。
一般來說，若在一開始令\(a^\frac{1}{n}=1+h\)，也能推導出\(\frac{a^x}{x}\geq c\cdot x^{n-1}\)，其中\(c\)是某個常數。所以一般來說，我們有
引理 1-1-1
對於任何\(A>0\), \(a>1\)，有 \[ \frac{a^x}{x^A}\to\infty\mbox{ when }x\to\infty \]
類似的還會有：
引理 1-1-2
對數函數的量級比任何\(x\)的次冪低。即對於所有\(\alpha>0\)，有 \[ \frac{\log x}{x^\alpha}\to 0\mbox{ when }x\to\infty \]
證明：令\(y=\log x\)，則 \[ \frac{\log x}{x^\alpha}=\frac{y}{(e^\alpha)^y} \] 故由上一個引理知其趨近於\(0\)。QED
大小O函數
定義 2：大O函數 (Big O)
給定函數\(f(x)\), \(g(x)\)，則若\(x\to\infty\)時有 \[ \frac{|f(x)|}{|g(x)|}\leq c<\infty \] 則記\(f(x)=O(g(x))\)。(或是\(x\)趨近某個點時，也可以定義類似的東西)
定義 3：小o函數 (Little o)
給定函數\(f(x)\), \(g(x)\)，則若\(x\to\infty\)時有 \[ \frac{|f(x)|}{|g(x)|}\to 0 \] 則記\(f(x)=o(g(x))\)。(或是\(x\)趨近某個點時，也可以定義類似的東西)