2011年3月17日 星期四

[Introduction To Algorithms] 第四堂: Divide-and-Conquer(3)

這堂課講 Divide and Conquer 的第二種方法,和第三中方法(講一部分)。 The tree-recursion method and The master method。


The tree-recursion method 基本上就是先畫圖把時間估算一下,然後再用 substitution 證明。












第三種方法在大部分的 Divide and Conquer 都可以用,以前對於 master 的解釋有點模糊,現在知道是 leaf 層和其他層的總和誰是老大的問題 (master)


接下來就是有三種情況討論

  • 小於
  • 等於
  • 大於
老師把觀念講出來,詳細證明自己要看教科書。




降~

沒有留言:

張貼留言