量級與複雜度函數

延續昨天，我們發現就連步驟數都不必估計得很精確，因此我們真正需要的是一個能找到最痛點的估計方法！

不過在此之前，先讓我介紹一個例子：
你 14 歲，是個學生。今天你因為一些特殊個人原因要請一個長假，因此老師決定出一個長期作業讓你假期期間也能持續練習。老師開了兩種作業方案給你選：

1. 每天算 100 題乘法
2. 第一天算 1 題加法、第二天算 2 題加法、第三天算 3 題加法...以此類推

假設你算一題乘法需要 100 秒，算一題加法需要 5 秒，你會選哪種作業?

假設到了第 N 天，方案 1 累計共消耗你 秒的時間算乘法；
方案 2 使用等差級數和公式可以算出，累計共會消耗你 秒算加法

如果 N = 3，則方案 1 累計消耗 30,000 秒、方案 2 累計消耗 30 秒，差了整整 1000 倍啊!你是不是覺得方案 1 明顯比較划算呢?

但如果 N = 30,000 終生假 呢？此時方案 1 累計消耗 300,000,000 秒、方案 2 累計消耗 2,250,075,000 秒，反超 7 倍之多喔！而且顯而易見的，當 N 持續變大它們差距也會不斷被拉開。

例如再給 N 加個 0，N = 300,000，此時方案 1 累計消耗 3,000,000,000 秒、方案 2 累計消耗 225,000,750,000 秒，現在反超 75 倍之多了！

我們這邊會說方案 2 的「量級」比方案 1 大(比較複雜)，因為儘管方案 1 一開始看起來比較糟糕，但隨著自變數的增長，最後量級的差距會顯現出來。

把剛剛的累計消耗時間換成步驟數、天數換成程式的輸入，會發現其實上面說的概念和昨天的步驟數估計是一樣的，演算法的步驟數也會有量級的差異，這可能導致某些演算法一開始乍看之下比較慢，但隨著輸入規模變大後性能反而比較好。

其實上面這個例子是從資訊之芽 算法班的影片借鑑而來的，所以不妨再借一個XD
好比一隻年幼的老虎和成年的土狗，一開始一定是土狗比較兇狠，但隨著時間增長，老虎將成長到土狗無法企及的程度，因此小時候的胖不是胖，所謂的成長性就是量級的概念！

最後來介紹一下接下來會常常用到的新名詞：複雜度，代表演算法中輸入值對應執行步驟數的函數，因為這代表了該演算法的輸入對問題的複雜程度的影響，因此該函數也被稱為時間複雜度；當然也有描述輸入值對應變數數量的函數，也就是空間複雜度。只是因為空間的分析一般來說較簡單，像昨天程式中的變數數量對應函數 f(n) = 2 基本上看一眼就出來了，因此這邊先專注在時間複雜度上。

不過其實通常一般表示複雜度時，並非剛好就是輸入對應步驟數的函數，因為如同前面說的，摒除一些不是那麼重要的因素，保留「最痛點」才是較好的做法。

就像剛剛的方案 1 累計耗時和方案 2 累計耗時分別為 和 一樣，其實如果你剛剛有跟著我算的話，你可能會發現方案 1 量級小的理由在於 N 每次被 +1 時都只是多 10000，但是方案 2 每次卻都會以 的倍率提高，這表示倍率會隨著 N 的成長提高。所以方案 1 前面的兩個 100 只是嚇嚇人而已，而方案 2 後面的 / 2 或 *5 對方案 2 整體來說也沒造成什麼決定性的影響，因此剛剛的例子中的兩個方案的「最痛點」分別會是 N 和 N(1 + N)。

方案 2 的倍數之所以是 倍是因為對於 當 K = N + 1 時， ，兩者相除等於

不過剛剛分析用的方法其實有點倚賴直覺的感覺，雖然結果沒錯，但為了應用更廣泛，我們需要更加精簡嚴謹、更加形式化估計方法，這就是我們下面要提到的。

量級與極限

以下所說的複雜度函數均代表之前說過的操作數函數，不過本章所用的複雜度表示法仍不屬於正規的表示法。這部分會在後面的文章提及，敬請期待

本節主要會解釋一下剛剛所謂的「量級」在數學上的表示方法。其實量級的概念就是成長性或潛力，所以我們在評估時要把眼光放長遠，要的不是過去某刻、不是當下此時、不是未來某日、而是那遙遠到無法抵達的未來！

而這樣的概念其實就和數學的「極限」一樣，因此我們也能用極限的方式來比較複雜度函數的量級。

極限小介紹

簡單說一下極限的概念，若函數 f(x) 的 x 在逼近 a 時的極限趨近於 L —— 這是說 x 是逼近 a、不是到達 a

此時則可以表示為 ，這就是極限的定義。

舉例來說，有函數 f(x) 定義如下：

說白話就是這個函數在 x 等於 0 時函數值等於 1；x 不等於 0 時函數值等於 0，很叛逆。

那此時它的極限 等於多少呢?別以為是 1 喔！因為我們關注的是自變數 x 不斷往 0 靠近、不斷靠近、距離小到一個不行、小到幾乎好像就到了卻沒有真正抵達時的函數值，因此

無限的計算規則

因為複雜度函數的估計需要考慮的是當輸入不斷變大的情況，這是趨近於無限的概念，因此這邊先稍微介紹一下極限中無限的運算規則，給定三個函數的極限如下：

然後根據極限的定義，要得到兩個函數一起運算過後的極限，可以先將兩函數個別的極限值取出，在進行相應運算。因此下面 5 式均成立：

前面四條其實滿好想像的，這邊舉一個例子說明：

現在舉辦了一場慘無人道馬拉松大會。假設函數代表馬拉松選手；極限值代表把選手的腿操爆到一步都動不了、再叫他跑他也只能躺在地上裝死後，此時他累計能跑的極限距離。

現在有兩選手 A 和 B，他們的極限距離分別是 M、N，他們一起在馬拉松中報名了四個項目，分別是加法、減法、乘法、除法：

1. 加法：成績為 A 和 B 從起點跑接力所能跑的最遠距離，結果明顯會是 M + N
2. 減法：成績計為叫 A 從起點往前跑跑到極限後再叫B往回跑跑到極限後與起點的距離，這距離是 M - N
3. 乘法：假設選手經過一天就能恢復體力。則叫 A 從起點開始，跑 M 天、每天必須跑到極限然後就地野營休息，隔天繼續跑。成績計為這樣下去到最後與起點的距離，這距離明顯會是 M * N
4. 除法：假設選手經過一天就能恢復體力。讓 A 從起點跑到極限，然後讓 B 跟著同方向跑到極限。若 B 跑不到 A 的位置，就讓 B 睡一天繼續跑，成績計為就這樣跑到最後 B 跑了幾次才趕上 A 的極限的次數。次數可以是有理數，例如 B 才跑到自己極限的一半就趕上 A 的極限了。這樣結果是 B 的 0.5 個極限。而次數的結果會是 M / N，這是相當顯而易見的

以上例子應該很直覺地解釋了四條運算規則的原理。

不過比較不直覺的是 h(x) 的極限是無限大是什麼鬼?然後第五條式子怎麼會變 0?

為了解釋，我們延續馬拉松的例子。你可以想像有一個選手 C，他乍看之下看普通人類一樣，但他其實是某個異次元的類人生物，他可以借助體內黃金迴旋永動機的能量源源不絕的為身體提供力量，因此他的字典裡沒有「累」。

那此時慘無人道馬拉松大會對他來說就沒有意義了，因為無論是加法賽、減法賽、乘法賽他都可以跑到讓比賽永遠結束不了，因此他的成績也只能被訂為「無限大」。這個成績沒辦法用正常的標準衡量，因為這是根本完賽不了所以才迫不得已定的標準。

但是除法賽就不一樣了！先開賽的人若是正常人類，則 C 追上他的極限後，這樣的次數該算多少？剛剛說根本無法評估 C 的極限距離，所以成績只能計為無限大，那一段有限的距離等於多少個無限大呢？因為無限大根本不是正常的數值，它只是象徵一種最大的概念而已，因此結果只能計為 0。

值得一提的是，要是今天從異次元又跑來了一個和 C 同種族的人 D 和 E，但 D 體內所建的是更高級的騎兵迴旋永動機，能量一樣用不完，但運轉功率比黃金迴旋高不少；E 的話就跟 C 一樣了。此時 C、D 和 E 的競賽結果如何呢?

2. 減法：因為三人情況特殊，因此改變賽制：改成選手在起點同時往反方向起跑，成績為兩人不斷跑下去所跑距離相減的值。此時若 C 和 D 比賽，結果一樣跑不完，但很明顯距離上 C 會被虐爆，成績只能計為負無限大。但 C 和 E 跑就比較特別了，因為兩人能量剛剛好一樣、速度也一樣，因此怎麼跑都會發現兩人相減為 0，因此成績可以被計為 0
3. 除法：因為三人情況特殊，因此改變賽制：改成選手同時從起點開始跑，看第一個選手的距離是第二個選手的距離的幾倍，採計的距離遠到選手的極限。此時若 D 和 C 一起比，會發現雖然一樣無法完賽，但 D 和 C 的距離會被拉開，且這被拉開的距離隨著時間的推移會漸漸被大。因為兩人都不是普通人，所以這距離可以無限的被拉開，因此成績只能一樣計為無限大；兩位選手的順序反過來的話就只能計為 0 了。至於 C 和 E 的話，因為兩人速度一樣，所以會看到跑起來時根本就黏在一起，且始終沒有分開的趨勢，因此成績只能訂為 1。

以上的舉例除了解釋了 h(x) 的極限是無限大的狀況和然後第五條規則變 0 的原因以外，還介紹了兩個極限值都為無限的函數的運算狀況。

有了基本認識後我們終於能開始進入量級的比較計算了

量級的比較

前面拖拖拉拉一大段解釋了數學極限的運算規則，在這邊套用到量級的比較上：

假設複雜度函數 f(n) = 3n + 5, g(n) = 2n + 7。則誰的量級比較大?量級是成長性，也可以說成長率，因此用兩函數極限的比率來評估是很恰當的:

其中在求極限時，將有理分式上下同除以最高次項是很常見的做法；另外中間那些項能變 0 的原因上一節已經解釋過了

這兩個函數成長的比率是 3/2 ，這表示 g 的量級就比較小嗎?回到前面統計程式碼步驟數量的段落，還記得我們有聊過步驟的重點只要符合與輸入無關、具有語意的片段即可，因此兩步併成一步完全是沒問題的。

這邊也一樣，若將這兩個複雜度函數的演算法實作出來，若 f 跟 g 一樣快，只要他每個步驟能快 3/2 倍即可，這樣的差距是可接受的，我們所不能接受的是那種無論如何都無法逾越的差距，因此我們認定 f 和 g 量級相同。

以下會比較一些量級不同的函數們：

• vs
  
  
  可以注意一個地方：極限若是出現了看起來像 ( 是某個有限的數)時，因為分母無限大，因此可以直接被視為 0，因此上式最後消去一下會變成 。
  然後極限下相除結果 0 意味著分母的函數在趨近於無限時會不斷變大、大到分子完全跟不上的程度，因此分母 量級比較大

• vs
  
  

  結果無限大，表示趨近於無限大的過程中，分子會大到分母完全無法與之相比的程度，因此 的量級較大
  我知道倒數第三步可能讓人有點難以接受，就是極限 是怎麼推導的?其實這用羅畢達法則算出來的，只是礙於篇幅原因，因此這邊不會介紹，請各位只能先這樣接受了QQ
  不過這結果是很直觀的，因為對數函數的圖形越往上就會越平緩，而且平緩的程度是根據當下的函數值決定的(這部分參考對數的定義)，而就算是根號的函數，如： 這種，看起來增長慢到一個難以置信的多項式函數，量級都還是會大於對數函數，以為我在唬爛?來看看在數學圈子廣受歡迎的數學計算引擎 WolframAlpha的計算結果 ，結果是無限大，代表這個多項式始終能超越對數函數。只不過在這個例子中，超越的那一瞬間可能得發生在一個大到不行的 n 了...

• vs
  
  因為化簡後的極限內還是含有會變大的函數 ，因此結果為無限大。 的量級較大

• vs
  這邊可以使用「夾擠定理」來解決，夾擠定理是用在當你想求函數 的極限時，你可以找找看兩個函數 和 ，此時假設區間 為包含我們要趨近的點 的區間，讓 成立，同時 ，則 ，而在我們的例子中 。
  
  
  
  此時有 且
  
  
  除此之外還可以使用史特靈公式來近似階乘函數後計算，不過一樣礙於篇幅原因，這邊依靠 wolfram大法。結論都是 的量級較大。
  不過這還是有直觀一點的理解方式的，就是當 時， 只是單純不斷乘以 100，但 則會 ，差距會被拉開

• vs
  
  因為 ，因此當次方上去後會不斷變小，結果會是 0， 的量級較大。
  可以稍微記住一下這個結論：底數不同的指數函數量級不同，等等可以對比一下

• vs
  
  （上面利用了換底公式化簡式子）
  結果為有限的常數，像前面的 ，因此兩者量級一樣。
  這個結論代表：底數不同的對數函數量級相同，這和指數函數不一樣喔！
  這也為我們解答了為什麼我們前面計算極限中的對數都只是寫 而沒有寫底數?網路上教複雜度的文章可能會說"電腦中會用到的對數大多是2，因此方便起見省略了"，這邊可以給出另外一個原因：因為就算底數不同、它們量級還是一樣，所以沒必要寫。

至此，我們已經學會利用數學的極限計算來比較量級了，但是數學算久了是不是感覺對數字有點麻木了？而且感覺很難體會所謂的「量級差距」實際到底會造成多大的差距？我懂！因此明天要開始做實驗了，請各位敬請期待！