Algorithm Chapter 3 - Growth of Functions

Asymptotic notation

$O$-notation

Figure 1. 圖中比較上面的那個函數是

$cg(n)$， 比較下面的函數是

$f(n)$。

$g(n)$ 是

$f(n)$ 的漸進上限。

• $O(g(n))=\{f(n):\text{there exist positive constants }c\text{ and }{n}_0\text{ s.t.}0\le f(n)\le cg(n)\text{ for all }n\ge n_0\}$
• 白話文：
  $O(g(n))$ 是一個函數的集合，這個集合裡面的每一個函數，在參數大到某一個程度 （
  $n_0$） 過後，其函數值都無法超過
  $g(n)$ 的某整數倍 （
  $c$）
• 此時，我們稱
  $g(n)$ 是
  $f(n)$ 的漸進上限 (asymptotic upper bound)
• 如果
  $f(n)\in O(g(n))$， 則我們會直接寫作
  $f(n)=O(g(n))$
• 舉例：以下函數都是在
  $O(n^2)$ 裏面的函數
  • $n^2$
  • $n^2+n$
  • $n^2+1000n$
  • $1000n^2+1000n$
  • $n$
  • $n/1000$
  • $n^{1.99999}$
  • $n^2/lg(lg(lg(n)))$

$\mathrm{\Omega }$-notation

Figure 2. 圖中比較下面的那個函數是

$cg(n)$， 比較上面的函數是

$f(n)$。

$g(n)$ 是

$f(n)$ 的漸進下限。

• $\mathrm{\Omega }(g(n))=\{f(n):\text{there exist positive constants }c\text{ and }{n}_0\text{ s.t.}0\le cg(n)\le f(n)\text{ for all }n\ge n_0\}$
• 白話文：
  $O(g(n))$ 是一個函數的集合，這個集合裡面的每一個函數，在參數大到某一個程度 （
  $n_0$） 過後，其函數值都不小於
  $g(n)$ 的某整數倍 （
  $c$）
• 此時，我們稱
  $g(n)$ 是
  $f(n)$ 的漸進下限 (asymptotic lower bound)
• 如果
  $f(n)\in \mathrm{\Omega }(g(n))$， 則我們會直接寫作
  $f(n)=\mathrm{\Omega }(g(n))$
• 舉例：以下函數都是在
  $\mathrm{\Omega }(n^2)$ 裏面的函數
  • $n^2$
  • $n^2+n$
  • $n^2-n$
  • $n^2+1000n$
  • $n^2-1000n$
  • $1000n^2+1000n$
  • $n^3$
  • $n^{2.00001}$
  • $n^2/lg(lg(lg(n)))$
  • $2^{2^n}$

$\mathrm{\Theta }$-notation

Figure 3. 圖中的函數由上到下是

$c_{2}g(n)$，

$f(n)$ 和

$c_{1}g(n)$。

$g(n)$ 是

$f(n)$ 的漸進上下限。

• $\mathrm{\Theta }(g(n))=\{f(n):\text{there exist positive constants }{c}_1,c_2\text{ and }{n}_0\text{ s.t.}0\le c_{1}g(n)\le f(n)\le c_{2}g(n)\text{ for all }n\ge n_0\}$
• 白話文：
  $O(g(n))$ 是一個函數的集合，這個集合裡面的每一個函數，在參數大到某一個程度 （
  $n_0$） 過後，其函數值都會介於
  $g(n)$ 的某整數倍 （
  $c_1$） 到另一個整數倍 （
  $c_2$） 之間
• 此時，我們稱
  $g(n)$ 是
  $f(n)$ 的漸進上下限 (asymptotic tight bound)
• 如果
  $f(n)\in \mathrm{\Theta }(g(n))$， 則我們會直接寫作
  $f(n)=\mathrm{\Theta }(g(n))$
• $f(n)=\mathrm{\Theta }(g(n))$， 若且唯若
  $f(n)=O(g(n))\wedge f(n)=\mathrm{\Omega }(g(n))$

$o$-notation

• $$\begin{gathered} o(g(n))=\{f(n):\text{for all positive constants }c>0\text{, there exists a constant }{n}_0>0 \\ \text{ such that }0\le f(n)<cg(n)\text{ for all }n\ge n_0\} \end{gathered}$$
• 白話文：
  $o(g(n))$ 是一個函數的集合，無論
  $g(n)$ 乘上哪一個正數 （
  $c$），這個集合裡面的每一個函數總是會從某個數字開始 （
  $n_0$），其函數值永遠都小於（沒有等於）
  $cg(n)$
• 更好懂的版本：
  ${\displaystyle \underset{x\to \mathrm{\infty }}{lim}\frac{f(x)}{g(n)}=0}$
• 舉例：以下函數都是在
  $o(n^2)$ 裏面的函數
  • $n^{1.9999}$
  • $\frac{n^2}{lg(n)}$
• 舉例：以下函數都不是在
  $o(n^2)$ 裏面的函數
  • $n^2$
  • $\frac{n^2}{1000}$

$\omega$-notation

• $$\begin{gathered} \omega (g(n))=\{f(n):\text{for all positive constants }c>0\text{, there exists a constant }{n}_0>0 \\ \text{ such that }0\le cg(n)<f(n)\text{ for all }n\ge n_0\} \end{gathered}$$
• 白話文：
  $o(g(n))$ 是一個函數的集合，無論
  $g(n)$ 乘上哪一個正數 （
  $c$），這個集合裡面的每一個函數總是會從某個數字開始 （
  $n_0$），其函數值永遠都大於（沒有等於）
  $cg(n)$
• 更好懂的版本：
  ${\displaystyle \underset{x\to \mathrm{\infty }}{lim}\frac{f(x)}{g(n)}=\mathrm{\infty }}$

Asymptotic notation in equations

略。

Comparisons of functions

Relational properties

• 遞移性 (Transitivity)
  • 若
    $f(n)=\mathrm{\Theta }(g(n))$ 且
    $g(n)=\mathrm{\Theta }(h(n))$， 則
    $f(n)=\mathrm{\Theta }(h(n))$
  • 於
    $O$、
    $\mathrm{\Omega }$、
    $o$、
    $\omega$ 同理
• 自反性 (Reflexivity)
  • $f(n)=\mathrm{\Theta }(f(n))$
  • 於
    $O$、
    $\mathrm{\Omega }$ 同理
• 對稱性 (Symmetry)
  • $f(n)=\mathrm{\Theta }(g(n))$， 若且唯若
    $g(n)=\mathrm{\Theta }(f(n))$
• 轉置對稱性 (Transpose Symmetry)
  • $f(n)=O(g(n))$， 若且唯若
    $g(n)=\mathrm{\Omega }(f(n))$
  • $f(n)=o(g(n))$， 若且唯若
    $g(n)=\omega (f(n))$

Comparisons

• 若
  $f(n)=o(g(n))$， 則
  $f(n)$ 漸進小於
  $g(n)$
• 若
  $f(n)=\omega (g(n))$， 則
  $f(n)$ 漸進大於
  $g(n)$
• 這樣的比較是沒有三一律的。雖然直覺上來說，我們可能會把
  $O$ 想成是
  $\le$，
  $\mathrm{\Omega }$ 想成是
  $\ge$， 但函數並不像一般的實數，有時候函數是無法拿來比大小的
  • 例如：
    $n^{1+sin(n)}$ 和
    $n$ 無法比大小，因為
    $1+sin(n)$ 會在 0 到 2 之間不斷振盪

Standard notations and common functions

Monotonicity

• 若
  $m\le n$ 時
  $f(m)\le f(n)$， 則我們說
  $f(n)$ 是單調遞增 (monotonically increasing) 的函數
• 若
  $m\le n$ 時
  $f(m)\ge f(n)$， 則我們說
  $f(n)$ 是單調遞減 (monotonically decreasing) 的函數
• 若
  $m<n$ 時
  $f(m)<f(n)$， 則我們說
  $f(n)$ 是嚴格遞增 (strictly increasing) 的函數
• 若
  $m<n$ 時
  $f(m)>f(n)$， 則我們說
  $f(n)$ 是嚴格遞減 (strictly decreasing) 的函數

後面是高中數學（？？？）