###### tags: `ADA 2.1` `Divide-and-Conquer`

# ADA 2.1 Divide-and-Conquer Introduction

## What is Divide-and-Conquer?

Divide-and-Conquer Introduction 各個擊破/分治法

* Solve a problem **recursively** *遞迴
* Apply three steps at each level of the recursion
1. **Divide** the problem into a number of subproblems that are smaller instances of the same problem(比較小的同樣問題)

**Divide** 將問題切成小的問題，input 數值比較小，可以直接解掉

2. **Conquer** the subproblems by solving them recursively
If the subproblem sizes are small enough
* then solve the subproblems **base case**
* else recursively solve itself **recursive case**

**Conquer** 切成小的問題後，比較容易思考有沒有比較簡單方式解決，如果還不夠小的就是一直切

* 直接解掉 **base case**
* 還不夠小要更小 **recurseive case**

3. Combine the solutions to the subproblems into the solution for the original problem

有些問題可能需要排序，因此需要將值回傳Combine
也就是把現在回傳的sub problem solution 組合成原本問題的solution

---

## Divide-and-Conquer Benefits
* Easy to solve difficult problems
** Thinking: solve easiest case + combine smaller solutions into the original solution

複雜的問題簡單化，藉由解決小的問題，組合成大的問題，比較容易思考大問題該怎麼去解，組合起來

* Easy to find an efficient algorithm
** Better time complexity

較好的time complextity (之後會教如何計算)

* Suitable for parallel computing (multi-core systems)

策略適合用在平行計算上
切小問題後，每個小問題可以平行算，雖然全部時間是一樣，但是透過拆解組合後，真實上花費時間比較短
＊不是所有演算法適合平行化，如果有需要順序的運算就不適合，只有在可以獨立運算的情況下適合

* More efficient memory access
** Subprograms and their data can be put in cache in stead of accessing main
memory

memory access上有效率
因為data可以存在cash裡面，可以互相利用