時間複雜度 — 函數間的比較
希望上次所提到的內容，各位讀者都有暸解到其中的精髓。
1. 幫助函數之間比較 — 數學公式與技巧
2. 簡單的例題（不同函數之間的時間複雜度的比較）
分析函數間的關係，目的在於要學會知道自己寫出來的程式，是不是真的可以使用（不會讓使用者等太久），或是當有兩個人用程式解決相同問題，老闆要怎麼知道誰的比較好，所以要靠今天的章節，來證明「我的演算法比較好！」。
而函數間的比較，我們可以想成是兩個函數在比賽，看哪一個成長速度會超過另一個。
1. 幫助比較函數間關係的簡單公式（方法一）
這邊取極限是在比較 f(n), g(n)的關係，所以
— 出現無限代表，f(n)贏了g(n)，因為f(n)跑得夠快，g(n)根本來不及追上，也可以想成說 g(n)根本來不及把 f(n)約掉，f(n)就直接往上衝（以圖形的角度來看）。
— 出現 0代表，代表g(n)贏了f(n)，因為 f(n)跑得很慢，g(n)衝太快，也可以想成說 g(n)很快就把 f(n)的值約掉，f(n)根本來不及增長。
上一章，我們有提到little-o, little-omega的定義。
這邊多加了一個theta的公式。
當n -> 無限大，將f(n)和g(n)取比值之後，趨近一個常數(const，就是一個數字)的話，我們稱f(n)是theta(g(n))。在解題目之前，請各位需要了解一些簡單的微積分概念。微分、羅比達法則、取對數。下方的解題，也會一一帶各位去使用。
介紹一下常用的技巧：
1).羅比達法則：
2). 取對數：
＊＊對數之間的關係＊＊
（如果不喜歡手寫的讀者，還請多多包涵，目前製作ppt技術尚未純熟。）
「 Log之間的轉換皆屬於常數的倍數 」
這邊想要表達，Log不管底是多少，他們之間的轉換皆屬於常數的倍數。也就是說在我們漸進函數的概念中，遇到什麼樣的Log，我們皆可以把它轉換乘以另一個為底的Log，因為只差常數項，在前一篇中有提及到，漸進函數只要一個大約的估計，倍數我們是不太考慮的。
從上面的結果得到用一些奇怪的Log後，換底也會是一個常數，所以在運算時，我們可以隨意地去交換Log的底。
2. 簡單例題
那就讓我們開始吧～
（這邊解題的方法，皆用手寫，因為還不太會用ppt寫公式）
第一題：（方法一）
第二題：（方法一）
像這題在我們推導到最後的時候，要在心裡偷偷的想（不要寫下來，可能會被扣分），因為f(n) < g(n)（因為一定是分母夠大贏了分子，最終答案才會是0），嗯嗯所以g(n)是嚴格上界。這時在趕緊把結論寫下來。
第三題：（如果微積分不強沒關係，我們有另一個方法！）
一開始看到這個方法，可能會覺得很錯愕，為什麼又有e跑出來（等等會解釋e的出現），他其實不難，只要用過一次就會覺得，好像還不賴。
我們用剛剛題目二的範例再做一遍。
為什麼會有e的出現？
Ans: 因為方法二的性質中有e的條件，所以我們在證明的最一開始先取了 ln，好讓最後可以被e給交換，回到原本題目給的函數。
什麼叫做以「大於等於多項式的成長速度」才對？
Ans: 這句話從另一個角度來看，就是代表我們取極限之後的結果不能是(含)對數或以下的增長速度。
＊如果記不起來的話，就想說因為 f(n) g(n)兩個分不出高下(為Theta的關係)，所以不能用方法二
圖五為「不能使用方法二」的例子：
這篇也花好大的心力才完成，如果有錯誤還請多多指教。
希望未來當我忘記要怎麼分析的時候，再回頭看看這篇，可以獲得滿滿的收穫。
那我們下次再見吧。
