GameLifeX

演算法效率的分析

2008-11-27T05:45:00.001+08:00

法則分析（The Design and Analysis of Computer Algorithms）

前言

法則分析，有時直接稱之為演算法（Algorithm），是一門用來學習如何解決問題，以及分析解題方法效率的學問。由於在學法則分析時，通常都會學到許多問題的解法（即演算法），因此直接將它視為學習演算法的學問也成。法則分析對於程式設計師與系統設計師是很重要的，如果不懂法則分析，對於一些常見的問題，往往不知有更有效率的演算法，同時也無法分析自己提出的演算法之效率性，因此讀者最好多多研究這門學問。在本文中，作者主要的目標是在說明各種解題的方法，並舉例說明其應用方式，以及所得演算法的效率分析。對於一般常見問題的演算法，如排序、搜尋等，將另以專文介紹說明。另外，法則分析中關於演算法 Lower Bound、Upper Bound（即找出演算法最佳與最差的效率極限），以及NP問題（即很難找到有效演算法的問題），由於太偏學術性研究，因此在本文中也省略不提。

邱奕南，2001/4/17

演算法效率的分析

演算法的效率分析，大致可分為時間效率和空間效率兩種，一般以O記號來表示，稱為該演算法的Order。其正式定義為：

一個演算法其執行所需的時間或空間為f(n)，而其Order為g(n)，n為輸入資料的數目，則存在常數c和m，使得f(n) <= c*g(n)，當n > m時。

例如一個演算法的時間效率為O(n^2)，表示當輸入的資料量為n時，執行該演算法所需的時間會以n^2的倍率成長。因此當再出現另一種演算法其時間效率為 O(nlogn)時，由於nlogn< a =" c"> c

2. T(n) = aT(n/c) + bn^2

T(n) = O(n^2), if a < a =" c^2"> c^2

以下我們便開始一一說明各種解題的方法。

一、直覺法

直覺法，便是依照人類最直覺的思考模式去找出問題的解法。這種方法往往都能找出可解決問題的演算法，尤其是面對從未遇過的問題類型的情況下。只不過以這種方式找出的演算法，其效率通常都不怎麼好。

例１：插入排序法（Insertion Sort）

想想看我們在玩撲克牌時是怎麼排序的？假設現在手上的牌已經依照花色和數字排好，再拿到一張牌時，我們會依序比較各個牌，找到適當的位置後再插入，插入排序法的觀念便和這種方式相同。假設目前已有n-1個排好的資料，再加入一個資料時，最糟的情況下，我們會比對n-1次才能找到要插入的位置，因此其時間效率 T(n)為：

T(n) = T(n-1) + n-1 = T(n-2) + n-2 + n-1 = ... = T(1) + 1 + ... + n-1 = T(1) + n*(n-1)/2

由於T(1)是個常數，因此取其最高次項，可得知其時間效率為O(n^2)。

例２：線性搜尋法（Linear Search）

在資料搜尋時，最直覺的方式便是一個一個找，一定能夠找到。於是在n個資料中搜尋時，在最糟的狀況下，我們必須比對n次，因此其時間效率為O(n)。

例３：矩陣乘法

對於兩個nxn的矩陣A和B相乘，最直覺的方式便是將它展開起來運算，於是我們需要n^3次乘法和(n-1)*n^2次加法，因此其時間效率為O(n^3)。

二、分割解決法（Divide and Conquer）

分割解決法是解決一般問題最有效率的方法。它先將問題分割成數個相同類型的小問題，然後再針對各個小問題找出解法，最後再將各小問題的答案綜整成整個問題最終的答案，因此使用這種方法找出的演算法，通常會運用到大量的遞迴呼叫（recursive call）。利用分割解決法所找出的演算法，只要在合併的效率上多加考量，則它的效率一般都會有不錯的表現。

例１：合併排序法（Merge Sort）

Merge Sort的概念，是將所有元素分成相同數目的兩堆，然後用遞迴的方式將這兩堆排好，最後再將這兩堆排好的元素合併排好。由於兩堆n/2數目的已排好元素要合併排好，其比對的次數為cn，c為一常數，因此可分析其時間效率T(n)為：

T(n) = 2T(n/2) + cn = 4T(n/4) + 2cn = 8T(n/8) + 3cn = ... = nT(1) + logn*cn

取其最高次項得知其時間效率為O(nlogn)。

例２：矩陣乘法

對於兩個nxn的矩陣A和B相乘，我們可將矩陣A和B分割成４個n/2xn/2子矩陣如下：

[Ａ１１　Ａ１２] [Ｂ１１　Ｂ１２] 　 [Ｃ１１　Ｃ１２]
[　　　　　　　] [　　　　　　　] ＝ [　　　　　　　]
[Ａ２１　Ａ２２] [Ｂ２１　Ｂ２２] 　 [Ｃ２１　Ｃ２２]

其中

C11 = A11*B11 + A12*B21
C12 = A11*B12 + A12*B22
C21 = A21*B11 + A22*B21
C22 = A21*B12 + A22*B22

若以乘法次數來分析，則其時間效率T(n)為：

T(n) = 8T(n/2) = 8^2 T(n/4) = 8^3 T(n/8) = ... = 8^logn T(1) = n^3 T(1)

可得知時間效率仍為O(n^3)，一點都沒有改善。但如果我們改良上述合併的方式成為：

m1 = (A12-A22)(B21+B22)
m2 = (A11+A22)(B11+B22)
m3 = (A11-A21)(B11+B12)
m4 = (A11+A12)B22
m5 = A11(B12-B22)
m6 = A22(B21-B11)
m7 = (A21+A22)B11
C11 = m1+m2-m4+m6
C12 = m4+m5
C21 = m6+m7
C22 = m2-m3+m5-m7

也就是多利用加法來少掉乘法的計算（因為乘法速度較慢），如此T(n) = 7T(n)，可得到其時間效率為O(n^log7)，約為O(n^2.81)。之後有人又提出其他的算法，可減少加法的次數，但乘法至少仍須7次，這點也已被人用數學證明了。然而這並不是這個演算法的極限，因為之後還有人使用不同的方法來解這個問題，而得到了一個O(n^2.734)的演算法。

例３：挑出n個數中的最大值和最小值

如果我們以直覺的方式先挑出最大值，再挑出最小值，則一共需要2n-3次比對，但若以分割解決法將之分成數量相同的兩堆，再從各堆中取出最大值和最小值，最後再從兩個最大值與兩個最小值去取得最大值與最小值，其所需的比對數為：

T(n) = 2T(n/2) + 2 = 4T(n/4) + 4 + 2 = ... = n/2 T(2) + n/2 + ... + 2

由於T(2)=1，因此T(n) = 3n/2 - 2。雖然兩者的Order都是O(n)，但使用分割解決法的效率仍然比直覺法來得好。

例４：快速排序法（Quick Sort）

Quick Sort的觀念，是隨便取一個元素a，然後將比a小的元素放在一堆，比a大的元素放在一堆，接著利用遞迴的方式依次將這兩堆元素排好。在最糟的情況下，所有剩下的元素都是在同一堆中，因此其時間效率T(n)為：

T(n) = T(n-1) + T(1) + n-1

由此解得T(n) = O(n^2)。不過快速排序法之所以被稱為快速，不是在它的最糟情況下，而是在平均情況下，它的比較次數會比其他排序法來得少。假設元素a出現在排好元素列中的各位置，其機率都是相同的，則：

T(n) = Σ(T(k-1)+T(n-k)) / n + n-1

解之得T(n) = O(nlogn)（過程略，有心的讀者可仔細推算）。

例５：Horner's rule

Horner's rule是將一個多項式f(x) = a(n) x^n + ... + a(1) x + a(0)，以f(x) = f'(x)*x + a(0)的方式遞迴計算，如此可得到乘法的次數為：

T(n) = T(n-1) + 1

得到T(n) = O(n)。事實上，Horner's rule在通用的情況下，已被證明其所需的乘法和加法都是最少的。

三、刪減搜尋法（Prune and Search）

刪減搜尋法，是在有多個可能通到答案的路徑上，依照目前得到的特性值，事先去除一些不可能的路徑，再由目前剩下的路徑繼續嘗試搜尋。它的精神所在便是如何有效地刪減路徑，就像分割解決法強調的如何有效的合併一樣。不過由於利用刪減搜尋法得出來的演算法，有時會和分割解決法所得的結果相同，因此這兩種方法也時常被混淆在一起。

例１：二分搜尋法（Binary Search）

對於一個已排序好的n個元素，要找到某個元素，最好的方法便是取正中間的元素進行比較，如此便可去除一半的元素不必再比較。依此可得到其時間效率為：

T(n) = T(n/2) + 1

得到T(n) = O(logn)。

例２：挑第k個元素（kth Selection）

在 n個數中挑選第k個最小的元素，若是先排序好再挑選，則最少需O(nlogn)，若以刪減搜尋法，先隨便挑出一個元素a出來，然後將比a小的放到S1中，和a相同的放到S2中，比a大的放到S3中。接著查看S1、S2、S3的元素數目，如果k落在S1中，則只要繼續找S1便可以了；若落在S2中，元素a便是所要的結果；若落在S3，表示S1、S2里面的元素都不可能了，修正k值再繼續找S3。如此在最糟的情況下，其時間效率為：

T(n) = T(n-1) + n-1

解之得T(n) = O(n^2)。不過在平均情況下，其時間效率是O(n)（由於解出過程頗複雜，在此省略，可參考前述之Quick Sort平均情況下的時間效率公式）。如果要增加最糟情況下的效率，最好的方法便是儘量挑到位在中央的元素a，如此才能刪減掉最多的元素。以下便是一種挑選方法：

將元素每r個分成一堆，r最好取5,7,9等較小的奇數（不可取3）。
對每堆元素，找出其實際的中央元素，組合成另一堆元素。
針對前述所得之元素堆，以遞迴方式繼續取得近似中央元素。
在數理上可證明由此方法得出的元素，至少有n/4個元素比它小，且至少有n/4個元素比它大，於是最糟情況下的時間效率函數，可寫成（第一個式子為挑近似中央元素，第二個式子為挑第k個元素）：

T(n) = [crn + T(n/r)] + [cn + T(3n/4)] = T(n/r) + T(3n/4) + cn

因此只要n/r+3n/4 <>的邊緣

遞迴結束的狀況便是：

Cost(k-1,j) = c(j,t) if 邊緣存在，或無限大 if 邊緣不存在

然後以Cost(1,s)進行遞迴計算，在計算過程中，即可找出最佳的路徑，其時間效率為O(n+e)，n為端點數目，e為邊緣數目。

作者 : chiuinan2(青衫) [ 貼文 3045 | 人氣 156152 | 評價 2879 ]Visual C++ .NET卓越專家VC++曠世奇才Visual Basic優秀好手資訊類作業求救卓越專家一般曠世奇才程式設計甘苦談優秀好手C++ Builder優秀好手C++頂尖高手Assembly優秀好手貼文超過3000則人氣指數超過150000點
[ 回應本文 ] [ 發表新文 ] [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
10/8/2004 10:09:57 PM
結語

除了上述的解題方法外，其實還有其他的解題法，例如局部搜尋法（Local Search）、解線性規劃問題（Linear Programming）的單工法（Simplex Method）、以及數值分析常用的逼近法等，這些有的會另以專文說明，有的則偏於複雜，甚少用到，不值得在此處大費周章的說明。

參考文獻

1. Fundamentals of Data Structures, Ellis Horowitz, 1984, 松崗
2. Combinatorial Optimization: Algorithms and Complexity, Christos H.Papadimitriou, 1982, 儒林
3. Algorithms, Rebert Sedgewick, 1983, 東南
4. Algorithms + Data Structures = Programs, Niklaus Wirth, 1976, 儒林
5. The Design and Analysis of Computer Algorithms, Aho, 1974, 開發

算法與數據結構——大整數的乘法

2008-11-27T05:30:00.001+08:00

大整數的乘法

問題描述

參考解答

設X和Y都是n位的二進制整數，現在要計算它們的乘積XY。我們可以用小學所學的方法來設計一個計算乘積XY的算法，但是這樣做計算步驟太多，顯得效率較低。如果將每2個1位數的乘法或加法看作一步運算，那麼這種方法要作O(n²)步運算才能求出乘積XY。下面我們用分治法來設計一個更有效的大整數乘積算法。

　

圖6-3 大整數X和Y的分段　

我們將n位的二進制整數X和Y各分為2段，每段的長為n/2位(為簡單起見，假設n是2的冪)，如圖6-3所示。

由此，X=A2^n/2+B ，Y=C2^n/2+D。這樣，X和Y的乘積為：

XY=(A2^n/2+B)(C2^n/2+D)=AC2ⁿ+(AD+CB)2^n/2+BD (1)

如果按式(1)計算XY，則我們必須進行4次n/2位整數的乘法(AC，AD，BC和BD)，
以及3次不超過n位的整數加法(分別對應於式(1)中的加號)，此外還要做2次移位(分別對應於式(1)中乘2ⁿ和乘2^n/2)。所有這些加法和移位共用O(n)步運算。設T(n)是2個n位整數相乘所需的運算總數，則由式(1)，我們有:

(2)

由此可得T(n)=O(n²)。因此，用(1)式來計算X和Y的乘積並不比小學生的方法更有效。要想改進算法的計算複雜性，必須減少乘法次數。為此我們把XY寫成另一種形式:

XY=AC2ⁿ+[(A-B)(D-C)+AC+BD]2^n/2+BD (3)

雖然，式(3)看起來比式(1)複雜些，但它僅需做3次n/2位整數的乘法(AC，BD和(A-B)(D-C))，6次加、減法和2次移位。由此可得:

(4)

用解遞歸方程的套用公式法馬上可得其解為T(n)=O(n^log3)=O(n^1.59)。利用式(3)，並考慮到X和Y的符號對結果的影響，我們給出大整數相乘的完整算法MULT如下:

function MULT(X，Y，n); {X和Y為2個小於2n的整數，返回結果為X和Y的乘積XY}
begin
S:=SIGN(X)*SIGN(Y); {S為X和Y的符號乘積}
X:=ABS(X);
Y:=ABS(Y); {X和Y分別取絕對值}
if n=1 then
   if (X=1)and(Y=1) then return(S)
                    else return(0)
       else begin
              A:=X的左邊n/2位;
              B:=X的右邊n/2位;
              C:=Y的左邊n/2位;
              D:=Y的右邊n/2位;
              ml:=MULT(A,C,n/2);
              m2:=MULT(A-B,D-C,n/2);
              m3:=MULT(B,D,n/2);
              S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
              return(S);
            end;
end;

上述二進制大整數乘法同樣可應用於十進制大整數的乘法以提高乘法的效率減少乘法次數。下面的例子演示了算法的計算過程。

設X=314l,Y=5327，用上述算法計算XY的計算過程可列表如下，其中帶^'號的數值是在計算完成AC，BD，和(A-B)(D-C)之後才填入的。

X=3141 A=31 B=41 A-B=-10

Y=5327 C=53 D=27 D-C=-26

AC=(1643)^'

BD=(1107)^'

(A-B)(D-C)=(260)^'

XY=(1643)^'10⁴+[(1643)^'+(260)^'+(1107)^']10²+(1107)^'

=(16732107)^'

A=31 A₁=3 B₁=1 A₁-B₁=2

C=53 C₁=5 D₁=3 D₁-C₁=-2

A₁C₁=15 B₁D₁=3 (A₁-B₁)(D₁-C₁)=-4

AC=1500+(15+3-4)10+3=1643

B=41 A₂=4 B₂=1 A₂-B₂=3

D=27 C₂=2 D₂=7 D₂-C₂=5

A₂C₂=8 B₂D₂=7 (A₂-B₂)(D₂-C₂)=15

BD=800+(8+7+15)10+7=1107

|A-B|=10 A₃=1 B₃=0 A₃-B₃=1

|D-C|=26 C₃=2 D₃=6 D₃-C₃=4

A₃C₃=2 B₃D₃=0 (A₃-B₃)(D₃-C₃)=4

(A-B)(D-C)=200+(2+0+4)10+0=260

如果將一個大整數分成3段或4段做乘法，計算複雜性會發生會麼變化呢?是否優於分成2段做的乘法？這個問題請大家自己考慮。