這章節主要在探討Recurrence 和 Divide and Conquer的關係
divide and conquer有三部曲,顧名思義 divide conquer 還有一個combine。
Divide -> partition array into 2 subarrays around pivot x.
Conquer -> recursively sort 2 subarrays
Combine -> Trivial
這時一定很好奇與recurrence有什麼關係。這關係可大的。以merge sort 做例子。首先,先把一個array拆成兩個array。再把拆出來的array再一次做分解。一直分解到最底層之後開始比較。比較完之後將結果回傳。回傳之後的值再做結合與整理。最後得到由小到大或由大到小整理好的一個array。
解決recurrences有三種方法。
1.substitution method
step1:
Guess the form of the solution.
step2:Use mathematical induction to find the constants and show that the solution works.
2.recursion-tree
3.master method
T(n) = aT(n/b) + f(n)
在課本4.1中,舉了一個生活中的例子,用divide and conquer來解決。寫了兩個function。前面那個沒有用到遞迴的概念,但後面的有。然後分析了用遞迴的比較迅速。4.2是說matrix multiplication 與 Strassen’s algorithm的關係。這部份在我下面附上的筆記裡有。後面就講上面所說的三個方法。第一個substitution method。重點就是在「猜」。猜出答案當然也需要經驗跟一些判斷的依據。這部份有舉一個例子來表現他猜的功力。畫遞迴樹這部份在我下列附的筆記裡有詳細說明。最後的master method,根本是數學的套公式。配對的功力,筆記也寫的很詳細,沒什麼特別技巧。
以上小弟分享心得,大大們請多多指教。
0 comments:
Post a Comment