Algorithms筆記11 - Divide and Conquer

分而擊之

聽起來很酷，這種策略有以下幾個特徵：

1. 分成許多一樣問題但是input size較小者：

一樣的subproblem很重要，跟greedy algorithm一樣，都必須是同類型的，這樣能解決小的，就能解決大的，例如把一個矩形面積拆成好幾個矩形來算：

但是不能拆成其他形狀，因為這就不是subproblem:

2. 各個擊破後，要把答案拼成原本大問題的答案，這是一個很大的特徵，所以除了切成不同size的subproblem之外，這些subproblems必須要剛好能組合成母問題答案，所以以下的分法是錯的，因為subproblems重疊了：

3. 根據1. 的特性，自然會形成recursive algorithms。

一個D&C linear search例子

這個例子其實沒有什麼divide and conquer 的好處，因為每個subproblem只是原本的input size - 1。這邊是用來解釋如何估算running time：

每次recursion level都做了O(1)的事情，最差會總共做了n次，所以是O(n)，或更精確地說是theta(n)。