複選題

5.下列哪些屬於「分治法(Divide and Conquer)」典型用法？
(A) Merge Sort
(B) Quick Sort
(C) Binary Search
(D) Counting Sort
(E) FFT(快速傅立葉變換)

【解題思路】

解這題只要掌握一句話：

分治法（Divide and Conquer）＝
把問題「切成小問題 → 分別解決 → 合併結果」。

典型分治法算法的三步驟是：

1. Divide（切分）

2. Conquer（遞迴解小問題）

3. Combine（合併結果）

經典例子包括：

• Merge Sort（合併排序）

• Quick Sort（快速排序）

• Binary Search（二分搜尋）

• FFT（快速傅立葉變換）

唯一不是分治法的是 Counting Sort。

因此答案為：
A、B、C、E

【逐步講解每個選項】

(A) Merge Sort — 合併排序

是分治法最標準、教科書等級的示範：

1. Divide：切成兩半

2. Conquer：對左右遞迴排序

3. Combine：合併兩個排序好的子序列
   → 100% 分治法

正確！

(B) Quick Sort — 快速排序

流程：

1. 選 pivot（基準）

2. Divide：把資料切成小於 pivot 和大於 pivot 的兩段

3. Conquer：對兩邊遞迴快速排序

4. Combine：拼回整體序列
   → 分治法核心案例

正確！

(C) Binary Search — 二分搜尋

邏輯：
每次將搜尋空間切成兩半，並遞迴往其中一半搜尋
→ 典型 Divide and Conquer

正確！

(D) Counting Sort — 計數排序

Counting Sort 是利用「計數桶」來排序，
它不需要把問題切成更小問題，也不需要遞迴或合併步驟。

它的邏輯是：

• 開一個陣列記錄每個值的出現次數

• 依計數結果輸出排序後的序列

不是分治法。

(E) FFT（快速傅立葉變換, Fast Fourier Transform）

FFT 的經典演算法 Cooley–Tukey FFT 也是用分治法：

1. 將 N 點訊號分成偶數與奇數位置

2. 各自遞迴做 FFT

3. 再將結果合併

→ 這就是 Divide & Conquer 的標準模式。

正確！

【延伸知識】

分治法（Divide and Conquer）常見代表演算法：

• Merge Sort

• Quick Sort

• Binary Search

• FFT

• Strassen Matrix Multiplication

• Karatsuba Fast Multiplication

• Closest Pair of Points（平面最近點）

分治法適合具有「子問題與母問題結構相似」的問題。

【記憶技巧】

一句口訣：

「切一半：二分搜尋；
切兩半：快排合併；
切奇偶：FFT。
記數不切→ Counting Sort。」

或更短版：

「快排、合併、二分、FFT＝分治；
記數排序≠分治。」

【常見錯誤】

1. 把 Counting Sort 誤以為是「排序法＝分類法」
   → Counting Sort 不是遞迴，也不是分治。

2. 忘記 FFT 其實用分治法
   → 很多人以為 FFT 很抽象，但其實就是 Divide → Conquer → Combine。