漸近符號

漸近記號$\Omega$

??$f(n)=\Omega (g(n))$ 當且僅當存在正的常數C和$n_0$，使得對于所有的$n\ge n_0$ ，有$f(n)\ge C(g(n))$。此時，稱$g(n)$是 $f(n)$的下界。
??根據符號$\Omega$的定義，用它評估算法的復雜度得到的是問題規(guī)模充分大時的一個下界。這個下界的階越高，評估越精確，越有價值。

例：設$f(n)=n^2+n$,則
$f(n)=\Omega (n^2)$，取$c=1,n_0=1$ 即可
$f(n)=\Omega (100n)$，取$c=1/100,n_0=1$ 即可
顯然，$\Omega (n^2)$作為下界更為精確。

漸進記號$\Theta$

??$f(n)=\Theta (g(n))$ 當且僅當存在正常數和$C_1,C_2,n_0$，使得對于所有的$n\ge n_0$, 有$C_1(g(n))\le f(n)\le C_2(g(n))$。此時，稱$f(n)$與$g(n)$同階。
??這種漸進符號是指，當問題規(guī)模足夠大的時候，算法的運行時間將主要取決于時間表達式的第一項，其它項的執(zhí)行時間可以忽略不計。第一項的常數系數，隨著n的增大，對算法的執(zhí)行時間也變得不重要了。

例：$3n+2=\Theta (n)$
$10n^2+4n+2=\Theta (n^2)$
$5\times 2^n+n^2=\Theta (2^n)$

漸進記號小$o$

??$f(n)=o(g(n))$當且僅當$f(n)=o(g(n))$和$g(n)\ne o(f(n))$，此時，$g(n)$是$f(n)$的一個絕對上界。
??小$o$提供的上界可能是漸近緊確的，也可能是非緊確的。（如：$2n^2=o(n^2)$是漸近緊確的，而$2n=o(n^2)$是非緊確上界。

例：$4nlogn+7=o(n^2)$

漸進記號小$\omega$

??$f(n)=\omega (g(n))$當且僅當$f(n)=\omega (g(n))$和$g(n)\ne \omega (f(n))$，此時，$g(n)$是$f(n)$的一個絕對下界。
??$\omega$表示一個非漸進緊確的下界。

例：$f(n)=n^2+n$，則$f(n)=$\omega$(n)$是正確的，$f(n)=$\omega$(n^2)$是錯誤的。

漸進記號大$\mathrm{O}$

??設$f(n)$和$g(n)$ 是定義域為自然數集上的函數。若存在正數$c$和$n_0$c和n_0c，使得對一切$n\ge n_0$ 都有$0\le f(n)\le cg(n)$成立，則稱$f(n)$的漸進的上界是$g(n)$，記作$f(n)=\mathrm{O}g(n)$。
??根據符號大$\mathrm{O}$的定義，用它評估算法的復雜度得到的只是問題規(guī)模充分大時的一個上界。這個上界的階越低，評估越精確，越有價值。

例：設$f(n)=n^2+n$，有
$f(n)=\mathrm{O}(n^2)$，取$c=2,n_0=1$即可
$f(n)=\mathrm{O}(n^3)$，取$c=1,n_0=2$即可

常見的時間復雜度關系

O(1)<O(log(n))<O(n)<O(nlogn)<O(n^{2})

??$O(2^n)$和$O(n!)$大于以上的所有時間復雜度，具體原因參考圖像。

時間復雜度計算：遞歸方程

??加、減、乘、除、比較、賦值等操作，一般被看作是基本操作，并約定所用的時間都是一個單位時間；通過計算這些操作分別執(zhí)行了多少次來確定程序總的執(zhí)行步數。一般來說，算法中關鍵操作的執(zhí)行次數決定了算法的時間復雜度。
??比較簡單的算法時間復雜性估計通常需要觀察在for、while循環(huán)中的關鍵操作執(zhí)行次數，在這里我們只討論一種比較復雜的時間復雜度計算問題：求遞歸方程解的漸近階的方法。遞歸式就是一個等式，代表了遞歸算法運算時間和n的關系，通過更小輸入的函數值來描述一個函數。那么如何求得遞歸算法的Θ漸進界呢？主要有三種方法。

代入法

??代入法是指自己猜測一個界，然后用數學歸納法進行驗證是否正確，這種猜測主要靠經驗，不常用。

迭代法

??迭代法是指循環(huán)地展開遞歸方程，然后把遞歸方程轉化為和式，使用求和技術解之。

套用公式法

??這個方法為估計形如：$T(n)=aT(n/b)+f(n)$ 的遞歸方程解的漸近階提供三個可套用的公式。要求其中的a≥1和b>1是常數，f(n)是一個確定的正函數。那么在三種情況下，我們可以得到T(n)的漸進估計式，懶得打公式，所以截圖。