漸進符號

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

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

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

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

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

漸進上界 Big O

正式定義

令複雜度函數 ， 成立若且唯若存在兩個正整數 與 使得對於所有的 ，當 時， 都成立。

直觀一點的解釋

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

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

再更直觀一點的解釋

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

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

範例

1. 
   當 ，則對於 ， 均成立，因此
2. 
   當 ，則對於 ， 均成立，因此
3. 
   當 ，則對於 ， ，因此

小觀察：

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

常見的 Big O

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

• ：表示執行時間是常數，與輸入無關
• ：表示對數時間複雜度
• ：表示線性時間複雜度
• ：表示線性對數時間複雜度
• ：表示平方時間複雜度
• ：表示立方時間複雜度
• ：表示指數時間複雜度
• ：表示階乘時間複雜度

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

常用定理證明

定理：若多項式函數 ，則

證明：

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

當 時，上式成立。

因此

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

漸進下界 Big Omega

正式定義

令複雜度函數 ， 成立若且唯若存在兩個正整數 與 使得對於所有的 ，當 時， 都成立。

直觀一點的解釋

眼尖的人可能會發現，正式定義的部分跟 Big O 有 9 成像，就連名稱「漸進下界」都超像的，它們兩個是什麼關係？

觀察定義可以發現，Big O 要求 再乘上一個常數後，可以在某數之後永遠大於等於 ；Big Omega 則是要求 在乘上一個常數後，可以在某數之後永遠小於等於 。

因此如果說 Big O 是天花板代表了一個上限、那 Big Omega 就是地板，代表了一個下限。也因為 Big Omega 是一個下限，因此它只要能小於等於 就可以了，所以在滿足的情況下可以任意地低。不過過度樂觀也不是好事，一般來說都會盡量抓最緊的下界。

其他的概念則都與 Big O 一模一樣，因此不重複說一次了。

再更直觀一點的解釋

已經夠直觀啦！

範例

1. 
   當 ，則對於 ， 均成立，因此
2. 
   當 ，則對於 ， 均成立，因此
3. 
   當 ，則對於 ， 均成立，因此

小觀察：

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

常見的 Big Omega

同 Big O，只不過 變成

常用定理證明

定理：若多項式函數 ，且 則

證明：

根據前面 Big O 證明的定理，可知必存在常數 使得 下有 。

因此，對於所有的 有

至此看起來可能沒什麼問題，但因為在 不夠大的時候，有可能 會變成 0 或負數，因此起始的位置 不可為 1。

此時直接令

之所以那樣設定 是因為 ，且分母再加一是為了確保能夠小於

則 可以保證為正整數，此時對於所有 ， 有

此時根據 Big Omega的定義，可以得知：

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

漸進嚴格緊界 Big Theta

名字我亂取的XD，只是為了統一一下而已

正式定義

令複雜度函數 ， 成立若且唯若存在三個正整數 與 使得對於所有的 ，當 時， 都成立。

直觀解釋

基本上就是 Big O 和 Big Omega 加在一起，對於複雜度的描述是最精準的，因為它同時作為上限加下限

範例

開始之前，想想 Big O 和 Big Omega 的定義，你會發現可以它們兩個加起來代表對於同時滿足 和 的函數 和 可以找到四個正整數： 使得 下有 ，這不就是 Big Theta 的定義？

因此除了乖乖找那四個正整數以外，要是已知 Big O 和 Big Omega 一樣，則可以如下操作：

1. 
   當 ，因為前面的範例算過，我們已知 且 ，所以
2. 
   當 ，因為前面的範例算過，我們已知 且 ，所以
3. 
   當 ，因為前面的範例算過，我們已知 且 ，所以

經過這幾個練習應該不難理解把 Big Theta 表示成 Big O + Big Omega 是很好的描述。

小觀察：

上面那樣也是對的喔！不過一般來說也都會把係數忽略掉，因為這樣寫比較簡潔、通用，這對於 Big O 和 Big Omega 也是一樣的。

常見的 Big Theta

同 Big O

常用定理證明

定理：若多項式函數 ，且 則

證明：

欸？還有必要證明嗎？

根據前面 Big O 和 Big Omega 的證明後，既然都知道了 且 ，這不就代表必定存在兩常數 和 ，使得對於所有的 有 ？

這個結論代表了複雜度函數為多項式函數的最高次項即可直接代表整個函數的上界+下界喔！

小結

其實漸進符號不僅限於我們今天討論的三個，還有其他如 little o 和 little omega 等。但因為 Big O 和 Big Theta 較常用，並且要理解 Big Theta 的概念，先瞭解 Big Omega 會比較好懂，因此我才選擇了這三個符號作為今天的重點。

有了這三個數學工具在手，我們就能夠更精確地分析和表示演算法的複雜度函數！

不過這邊容我懺悔一下，由於時間壓力和個人能力問題，中間定理證明的部分可能會有錯誤，因此若有人發現問題歡迎在留言區指正；或是有發現有些重要觀念我沒講到的，也歡迎各位在下面補充！

然而，對於一直跟隨這系列文章的讀者來說，可能會有一些疑問：
「為什麼要設計這麼多種漸進符號呢？如果 Big Theta 表示是最精確的，為什麼不只用它？」、
「雖然我知道怎麼分析複雜度函數，但實際在分析程式的複雜度時，是不是只能先取得它的步驟數函數？好麻煩喔！有沒有更好的辦法？」

而這部分就是我們明天要探討的主題了，還請各位敬請期待~