over 2 years ago

0 緣起

Divide and Conquer:分而治之法,又稱為各個擊破法。基本上就是把一個問題分成很多子問題,然後各自解決這些子題目(通常是用遞迴方法),接著再把這些子題目組合得出原本問題的解。

1 快速冪問題

給定 以及正整數 ,請計算 之值。

說明

的時候,我們知道答案會是 (若 )。當 的時候,我們知道如果 是偶數,那麼只要能夠算出 ,就可以得出 。若 是奇數,則我們可以先算出 ,然後利用 就可以得到我們要的解了。

兩種變化型態

通常我們會想要計算整數 次方除以 的餘數。我們有兩種 Divide and Conquer 的方式:一種是「先遞迴再相乘」,另一種是「先相乘再遞迴」。

先遞迴再平方

int bigmod(int x, int n, int p) {
    if (n == 0) return 1 % p;
  int a = bigmod(x, n/2, p);
  return a*a%p*(n%2? 1 : x)%p;
}

先平方再遞迴

int bigmod(int x, int n, int p) {
    if (n == 0) return 1 % p;
  return bigmod(x*x%p, n/2, p)*(n%2? 1 : x)%p;
}

超心機 Case:
另外還有一種情況,若輸入的 是 64-bit 整數,那我們要注意乘法是否溢位。

分析

由於乘法和可能的取模運算相對花費時間,我們衡量這個演算法的時間好壞,基本上可以著重於乘法的計算次數。注意到當 是奇數時,每個遞迴呼叫我們必須花兩次乘法。若 為偶數,我們則需要一次乘法。因此整個演算法所需要的乘法次數為 寫成二進位後有多少個

註記

我們也可以不寫遞迴,採用 bottom-up 的方式計算 ,通常我們會把這樣的方法(或技巧)稱為倍增法(doubling trick)。這樣的想法會不斷地在各式各樣的演算法裡頭出現。

2 應用在矩陣上

假設我們今天想要計算一個矩陣 次方,也可以用完全一樣的概念。

3 應用在多項式上

假設我們今天想要計算一個 次多項式的 次方,比方說 ,那麼計算 的時候就可以利用「倍增」或「分治」的概念。假設一個 次多項式和 次多項式相乘,所需要的時間為 ,那麼計算 次多項式的 次方需要花費多少時間呢?

首先我們假設在最平凡的情形下,我們花 的時間做多項式相乘。

讓我們來試試看「先遞迴再平方」的策略:假設時間為 我們可以列式:

這樣解得

如果是「先平方再遞迴」呢?假設時間為 我們可以列式:

這樣解得

4 思考問題

  1. 如果我們今天不模 取餘數,要做大數計算,請問「先遞迴再平方」跟「先平方再遞迴」何者效率較佳?為什麼?
  2. 如果今天有一個比較快的多項式相乘作法(請參考 CLRS 第 30 章),,那麼「先遞迴再平方」與「先平方再遞迴」的時間複雜度分別為何?
← Hello World 分而治之法(二):尋找極小值 →
 
comments powered by Disqus