Day 5 漸進符號什麼的最討厭了！

2023 iThome 鐵人賽

DAY 5

自我挑戰組

15th鐵人賽資料結構與演算法廢文貓咪複雜度

445 瀏覽

漸進符號

其實如果有看完前四天的文章並有試著跟著練習的話，你對時間複雜度應該有基本的感覺了~~就像折斷HB鉛筆會發出啪的一聲一樣理所當然~~

不過接下來說的漸進符號可以說是一種數學工具，一般用於表示演算法的時間、空間複雜度。它不像我們前幾天那樣自己倚賴直覺進行的估計，而是能從步驟數函數中提取出代表了該複雜度量級的重要因素，並適當忽略掉一些相對沒那麼重要的項和係數，讓我們能夠更精確地分析和比較不同演算法的效率。

今天不會把全部的符號都介紹到，僅介紹較常用的三個：
Big O（ $\mathcal{O}$ ）、Big Omega（ $\Omega$ ）、Big Theta（ $\Theta$ ）

最後我們再快速地從最一開始做的分析開始回顧一下，並簡短說一下所謂的「漸進符號」在做的事情：

從原本現實環境中的程式出發，假設出「步驟」的概念並從中觀察出複雜度函數後，接著理解量級的概念、並學習找出對函數量級最大的因子，並進一步忽略掉函數中量級較低的項，使其作為常數因子被消去

令複雜度函數 $f(n)$ ， $f(n)=\mathcal{O}{(g(n))}$ 成立若且唯若存在兩個正整數 $c$ 與 $n_0$ 使得對於所有的 $n$ ，當 $n\ge n_0$ 時， $f(n)\le c\cdot g(n)$ 都成立。

其實它主要就是兩個觀念：

之前不是說過對於兩函數，量級較大的函數只要自變數上升到一定的程度就絕對能超越另一函數嗎？所以 Big O 其中一個條件就判定若有一個函數 $g(n)$ 從 $n_0$ 以後都能夠大於或等於 $f(n)$ ，就代表 $\mathcal{O}{(g(n))}$ 可以作為 $f(n)$ 的漸進上界
還記得在 Day 3 算極限那邊，我們有遇到兩函數相除後極限是有限的數字（常數）的範例嗎？那時候說因為有限的差距是可以接受的，而且這個差距也不會隨著輸入的再度變大而拉開，因此兩者量級一樣。
而 Big O 也利用這個概念，你說 $g(n)$ 總是差 $f(n)$ 一點？沒關係！它定義若有一個函數 $g(n)$ 乘以一個「常數」 $c$ 之後能大於或等於 $f(n)$ ，再加上上一點的條件成立的情況下， $\mathcal{O}{(g(n))}$ 可以作為 $f(n)$ 的漸進上界

也可以從名稱的角度來解釋，Big O 被稱為漸進上界是有理由的。

「漸進」就跟高中數學出現過的漸進線意思很像，只是今天的線不一定是常數函數或直線，而可以是一個函數、而且兩個函數不一定會像漸進線一樣到後面幾乎貼在一起，有可能會分開走。只不過他們之間的距離無關乎輸入，基本上都可以以常數倍表示
「上界」講白話一點就是「天花板」、「上限」。不過這邊可以借天花板來說明上界的一個特性：一般來說你不會想特別挑高家中的天花板，為什麼呢？因為已經夠用了，但老實說高一點也沒差。因為現在這樣都夠用了，要是再更高一點當然還是夠用，只是很浪費沒必要而已。
上界也是一樣的，一般取上界都會盡量取「緊」一點，但老實說你取更高一點也是可以的，只是這樣有點太悲觀而已

$f(n)=3n+2$
當 $g(n)=n$ ，則對於 $n\ge2$ ， $3n+2\le 4n$ 均成立，因此 $3n+2=\mathcal{O}{(n)}$
$f(n)=10n^2+4n+2$
當 $g(n)=n^2$ ，則對於 $n\ge5$ ， $10n^2+4n+2\le11n^2$ 均成立，因此 $10n^2+4n+2=\mathcal{O}{(n^2)}$
$f(n)=6\cdot2^n+n^2$
當 $g(n)=2^n$ ，則對於 $n\ge4$ ， $6\cdot2^n+n^2\le7\cdot2^n$ ，因此 $6\cdot2^n+n^2=\mathcal{O}{(2^n)}$

小觀察：

上面三點這樣也是對的喔！不過如同前面說過，一般來說會抓最緊的上界就是了

雖是以時間複雜度為例，但對於空間複雜度也是一樣的

以上都是最常見的時間複雜度，等之後開始學演算法之後，就會發現大部分常見演算法的時間複雜度幾乎都在上面

定理：若多項式函數 $f(n)=a_mn^m+\cdots+a_1n+a_0$ ，則 $f(n)=\mathcal{O}{(n^m)}$

證明：

$f(n)\le\sum_{i=0}^{m}{| a_i| n^i}$

此時將最大的 $n^m$ 提出來，此時加總符號內的所有 $n$ 的次方會變成負的

$\sum_{i=0}^{m}{| a_i| n^i}\le n^m\sum_{i=0}^{m}{| a_i| n^{i-m}}\le n^m\sum_{i=0}^{m}{| a_i|}$

當 $n\ge 1$ 時，上式成立。

因此 $f(n)=\mathcal{O}{(n^m)}$

所以以後找複雜度函數為多項式函數的 big O 時，只要取最高次項即可喔！