-
分治
鎖定
- 中文名
- 分治
- 外文名
- Partition
- 外文名
- Divide-and-Conquer
- 適用於
- 合併問題分解等
- 步 驟
- 劃分步等
分治分治法
分治適用條件
採用分治法解決的問題一般具有的特徵如下：
1. 問題的規模縮小到一定的規模就可以較容易地解決。
2. 問題可以分解為若干個規模較小的模式相同的子問題，即該問題具有最優子結構性質。
3. 合併問題分解出的子問題的解可以得到問題的解。
4. 問題所分解出的各個子問題之間是獨立的，即子問題之間不存在公共的子問題。
分治設計步驟
1. 劃分步：把輸入的問題劃分為k個子問題，並儘量使這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
