Algorithm lecture 4

這章節主要在探討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，根本是數學的套公式。配對的功力，筆記也寫的很詳細，沒什麼特別技巧。

以上小弟分享心得，大大們請多多指教。