分治

分治，字面上的解釋是“分而治之”，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併。在計算機科學中，分治法就是運用分治思想的一種很重要的算法。分治法是很多高效算法的基礎，如排序算法（快速排序，歸併排序），傅立葉變換（快速傅立葉變換）等等。

基本介紹

• 中文名：分治
• 外文名：partition
• 適用於：合併問題分解等
• 步驟：劃分步等

分治法

在求解一個輸入規模為n，而n的取值又很大的問題時，直接求解往往非常困難。這時，可以先分析問題本身所具有的某些特性，然後從這些特性出發，選擇某些適當的設計策略來求解。這種方法，就是所謂的分治法。

適用條件

採用分治法解決的問題一般具有的特徵如下：

1. 問題的規模縮小到一定的規模就可以較容易地解決。

2. 問題可以分解為若干個規模較小的模式相同的子問題，即該問題具有最優子結構性質。

3. 合併問題分解出的子問題的解可以得到問題的解。

4. 問題所分解出的各個子問題之間是獨立的，即子問題之間不存在公共的子問題。

設計步驟

1. 劃分步：把輸入的問題劃分為k個子問題，並儘量使這k個子問題的規模大致相同。

2. 治理步：當問題的規模大於某個預定的閾值n0時，治理步由k個遞歸調用組成。

3. 組合步：組合步把各個子問題的解組合起來，它對分治算法的實際性能至關重要，算法的有效性很大地依賴於組合步的實現。

分治法的關鍵是算法的組合步。究竟應該怎樣合併，目前沒有統一的模式，因此需要對具體問題進行具體分析，以得出比較好的合併算法。

大整數乘法

通常，在分析一個算法的計算複雜性時，一般將加法和乘法運算當作是基本運算來處理，即將執行一次加法或乘法運算所需的計算時間，看作一個僅僅取決於計算機硬體處理速度的常數。

然而，在有些情況下，需要處理數值很大的整數，這些數值無法在計算機硬體能直接表示的範圍內進行處理。如果要精確地表示大整數的數值並在計算結果中要求精確地得到所有位數上的數字，就必須用軟體的方法來實現大整數的算術運算，即用分治法實現大整數的運算。另外，分治法實現大整數運算，可以大大提高運算效率。

設兩個n（na，nb）位d進制數A、B相乘：

當位數n為偶數時，將數拆分為兩段等長的數段，高位段為H，低位段為L，則有

A=Ha*d^(n/2)+La B=Hb*d^(n/2)+Lb

當位數n為奇數時，可在數的首位前添0，使數的位數為偶數，然後將數拆分為兩段等長的數段。

例如，計算2進制數1010與1110的乘積。步驟如下：

（1）：1010=10*2^(2)+10 1110=11*2^(2)+10

（2）：1010*1110=（10*2^(2)+10）*（11*2^(2)+10）=10*11*2^(4)+10*11*2^(2)+10*10*2^(2)+10*10

（3）：1010*1110=（1*2^(1)+0）*（1*2^(1)+1）*2^(4)+（1*2^(1)+0）*（1*2^(1)+1）*2^(2)+（1*2^(1)+0）*（1*2^(1)+0）*2^(2)+（1*2^(1)+0）*（1*2^(1)+0）=2*3*16+2*3*4+2*2*4+2*2=140