星期日, 11月 30, 2008

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

張貼留言