Time Complexity

這個問題非常的簡單，不過最近在對這個做練習，我做個簡單的筆記好了。

Algorithm所提的Complexity分為Space Compleity和Time Complexity

先談談Space Complexity，我覺得爭議還蠻大的，以fundamental of data structure in C/C++裡面所提及的計算，皆以programming language所佔用的記憶體做為計算，這對於新一代的程式語言，並不是具有良好定義，所以我想就此略過。

而Time Complexity的計算方法，可參考OOPS: Introduction to Algorithm 2005 Spring, Asymptotic Notation (這一堂課到2008都有，老師都同一個，可以看 這裡)。

而對於Recurrences Time Complexity的方法有如下幾種

• Substitution method: 代入然後猜測最後的結果
• Recursion tree: 把整個Recursive的狀況畫出來，依序得到一個結果。
• Mater Method: 當T(n) 符合某個型式時即可使用。

最有趣的是Master Method，定義如下。

簡而言之，就是要比較n^{log_b^a}和f(n)的大小，那個函數的成長速度較快，就取用那一個，當然，這只是一個大概的描述，因為當兩者成長速率相似時(Case 2，允許差一個log^k_n)，蠻常聽到有人叫他"老大定理"，其實我比較喜歡Master翻譯成"主要"，似乎會更為貼切。

至於其於兩個方法，Recursion Tree本身最主要的重點為，這顆tree不可能長成一個balanced tree，所以很難算出很直接的值，大部分都是算出整顆樹的高度，用逼近法算出Time Complexity。而Substitution method也很直觀，帶入後觀看規律，猜出公式即可得證哩

---
感覺上很像隨便寫寫XD