- 註冊時間
- 2006-10-8
- 最後登錄
- 2019-6-20
- 主題
- 查看
- 積分
- 1306
- 閱讀權限
- 110
- 文章
- 1343
- 相冊
- 0
- 日誌
- 1
  
狀態︰
離線 
|
演算法必須滿足以下五個條件：
1. 輸入(input)：可以由外界輸入0個、1個或多個以上的資料。
2. 輸出(output)：至少要有1個以上的輸出。
3. 明確性(definiteness)：每個步驟都必須是明確而不含糊的。
4. 有限性(finiteness)：必須在有限步驟內結束。
5. 有效性(effectiveness)：每一個步驟必須是基本的(可行的)，也就是說，即使我們僅僅具有紙和筆也可以執行這些步驟。
演算法(algorithm)名稱來自於”al-Khwarizmi”，這是一個阿拉伯數學家(Abu Jafar Muhammad ibn Musa al-Khwarizmi，西元825年)的名字的最後一部份，此數學家將印度所發明的十進位數字記號傳入阿拉伯地區(稍後傳入歐洲並成為現今我們使用的數字記號)，並且著有一本名為”ilm al jabr w’al-muqabala”的書籍，此書有系統地討論一元二次方程的解法，啟發了代數學的發展。此書在12世紀被翻譯為拉丁文，名為Algebra et Almucabala， (Algebra源自阿拉伯書名中之al jabr)，而成為代數學(algebra)一字的由來。
演算法的表示
一般我們使用自然語言(中文或英文等語言)、流程圖(flow chart)、虛擬碼(pseudo code)或高階程式語言(high level programming language)來表示演算法。例如，以下的例子是同時使用自然語言(中文與英文)描述一個古老的演算法 歐幾里德演算法(Euclid Algorithm)。歐幾里德演算法(Euclid Algorithm) 大約在西元前300年由希臘數學家歐幾里德提出，用於求出二個整數的最大公因數(GCD, Greatest Common Divisor)。
演算法Euclid: 已知二個正整數m及n，找出此二數的最大公因數(也就是能同時整除m及n的最大正整數)
E1.[找出餘數] 求出m除以n的餘數，並記錄於r。
E2.[餘數為0嗎？] 如果r=0則停止，輸出n為GCD。
E3.[互換] 設定m=n,n=r，並跳至步驟E1。
在本書中，我們採用虛擬碼及Java程式語言來表示演算法。虛擬碼以一種混雜著自然語言與高階程式語言結構的方式來描述演算法，試圖達到簡潔易讀、容易分析，而且也容易轉換為高階程式語言的目的。本書採用Goodrich及Tamassia在”Data Structures and Algorithms in JAVA”一書中所提出的虛擬碼格式來表達演算法，在本書後面的章節所稱的虛擬碼指的都是這種虛擬碼。
Goodrich及Tamassia所提虛擬碼的撰寫規則如下：
方法宣告：以 Algorithm 方法名稱(參數1,參數2,…) 來宣告一個演算法並指明其參數。
設定動作：以 ← 表示，可以將一個算式之值指定給某一個變數。
相等比較：以 = 表示，可以比較二個算式是否等值。
決策結構：以 if條件then條件為真的動作(true-action)else 條件為偽的動作(false-action) 來表示，並以縮排來表示所有包含在true-action及false-action的所有指令。
while迴圈：以 while條件do動作 來表示，並以縮排來表示所有包含在迴圈中的所有指令。
repeat迴圈：以 repaet動作 until條件 來表示，並以縮排來表示所有包含在迴圈中的所有指令。
for迴圈：以 for迴圈範圍及變動 do 動作 來表示，並以縮排來表示所有包含在迴圈中的所有指令。
陣列元素索引：以 A[i] 代表陣列A索引值為i的元素，一個有n個元素的陣列，其元素索引值為0,1,…,n-1。
方法呼叫：以 物件.方法(參數…) 來代表。注意，當物件是明確的時候，物件可以省略不寫。
方法返回:以 return 方法返回值 來代表。
例如，以下就是使用虛擬碼來描述歐幾里得演算法的例子：
Algorithm Euclid(m, n):
Input:二個正整數m及n
Output:m及n的最大公因數(GCD)
r←m%n
while r0 do
m←n
n←r
r←m%n
return n
使用虛擬碼表示演算法可以方便演算法的分析，增加演算法的易讀性，並且可以方便的轉變成可以直接在電腦上執行的程式語言程式碼。例如，以下為將以虛擬碼表示的歐幾里德演算法轉換為Java語言程式碼的例子：
int Euclid(int m, int n) {
int r=m%n;
while (r!=0) {
m=n;
n=r;
r=m%n;
}
return n;
}
上例中的Java語言程式碼以方法(method)的結構表示了Euclid演算法。然而，要使上列的演算法能正確的執行，必須將上述的程式碼再進一步撰寫成Java語言中的類別(class)，並加上一些輸入與輸出敘述之後才可以進行編譯及執行動作。本書採用以下的格式來表示演算法的Java語言可執行型式。
範例程式(檔名：EuclidAp.java)
1: //檔名:EuclidAp.java
2: //說明:此程式可輸入二個整數，並以歐幾里得演算法求其最大公因數(GCD)
3: import javax.swing.JOptionPane;
4: public class EuclidAp {
5: public static void main(String[] 參數){
6: int 整數m,整數n,最大公因數;
7: String 輸入字串,顯示字串1,顯示字串2;
8: 輸入字串1=JOptionPane.showInputDialog("請輸入正整數m？");
9: 輸入字串2=JOptionPane.showInputDialog("請輸入正整數n？");
10: 整數m=Integer.parseInt(輸入字串1);
11: 整數n=Integer.parseInt(輸入字串2);
12: 最大公因數=Euclid(整數m, 整數n);
13: 顯示字串="整數"+整數m+"與整數"+整數n+"的最大公因數為"+最大公因數;
14: JOptionPane.showMessageDialog(null,顯示字串);
15: System.exit(0);
16: } //方法:main() 定義區塊結束
17: static int Euclid(int m, int n) {
18: int r=m%n;
19: while (r!=0) {
20: m=n;
21: n=r;
22: r=m%n;
23: }
24: return n;
25: }
26: } //類別:閏年測試 定義區塊結束
執行結果(命令視窗指令：java EuclidAp)
範例程式1-1.歐幾里德演算法執行程式。
如何撰寫、編譯並執行Java程式並是本章要探討的範圍，讀者可以參考「附錄一」( Java語言概要)，以得到撰寫Java語言程式的基本知識，或參考作者的另一本著作，「中文Java程式設計」以獲得足夠的參考資料。
演算法的分析
一個演算法的好壞，通常由以下幾點來分析：
1. 正確性(correctness):演算法是否能產生正確的結果。
2. 完整性(completeness)：演算法是否能考慮所有的輸入情況。
3. 簡單性(simplicity)：演算法是否簡單易懂。
4. 有效性(effectiveness)：演算法的執行是否有效率(快速)。
在上列的因素中，正確性是必要的條件。而除此之外，我們大都以演算法的有效性來衡量其優劣。一個演算法是否有效，一般以演算法的其執行速度與所佔用的記憶體空間大小來衡量。在學理上，我們使用時間複雜度(time complexity)及空間複雜度(space complexity)來評估演算法的執行速度與佔用記憶體空間，由於記憶體的價格日趨便宜，因此，空間複雜度對演算法的影響也越小，在本書中，我們也是比較重視時間複雜度的評估。
演算法的時間複雜度分析分為以下三種：
最佳狀況(best case)時間複雜度:考慮演算法執行時所需要的最少執行步驟數。
最差狀況(worst case)時間複雜度:考慮演算法執行時所需要的最多執行步驟數。
平均狀況(average case):考慮所有可能狀況下演算法執行的平均步驟數。
一般而言，演算法的時間複雜度分析中，平均狀況時間複雜度最難求取，因而，在有些狀況我們只考慮求得最佳狀況時間複雜度及最差狀況時間複雜度。而最差狀況時間複雜度又最為有用，因為這項複雜度可以讓我們了解演算法在最壞的情況下需要執行多少時間。
我們舉以下檢查一個整數是否為質數的演算法為例子來作說明。針對一個大於1的正整數而言，所謂質數(prime)是指除了1和本身之外沒有其他因數的整數，例如，3、5、7等整數為質數，而4、6、8等整數不是質數(因為2是4、6、8等整數的因數)：
Algorithm Prime1(n):
Input:一個大於2的正整數n
Output:true或false(表示n是質數或不是質數)
for i=2 to n-1 do
if (n%i)=0 return false
return true
1既不是質數也不是非質數，而2是最小的質數也是唯一一個為偶數的質數。
我們可以看出，輸入大於2的任意正整數n，若n是質數，則演算法Prime1需要執行整數除法求餘數(n%i)動作與整數比較((n%i)=0)動作n-2次，才可以知道n是質數。另外，若n為偶數，則演算法Prime1只要執行整數除法求餘數與整數比較動作1次就可以知道n不是質數。因此，我們很容易看出來，在最壞狀況下，演算法Prime1的執行速度與輸入的正整數n成正比；而在最佳狀況下，演算法Prime1的執行速度為1次。也就是說，演算法Prime1的最差狀況時間複雜度與輸入的正整數n成正比；而演算法Prime1的最佳狀況時間複雜度為1。至於演算法Prime1的平均狀況時間複雜度比較難分析，在此我們先省略。
一般而言，我們使用所謂的趨近記號(asymptotic notation)來分析演算法的複雜度，趨近記號考慮的是演算法在處理資料範圍趨近於無窮大時的狀況。在演算法的資料處理範圍較小時，不管是有效率(速度較快)或沒有效率(速度較慢)的演算法通常都可以很快的執行完畢，因此，我們僅分析演算法處理資料範圍非常大的狀況，這是為什麼分析演算法執行時間複雜度採取趨近記號的原因。
在演算法處理資料範圍趨近於無窮大的狀況下，演算法的執行時間複雜度會趨近於一個量級(order)。一般而言，演算法的執行時間複雜度是一個多項式，當演算法處理資料範圍趨近於無窮大時，時間複雜度的多項式中除了最高次方的項目外，其他的部分都可以被忽略；而同時，最高次方項目的係數也同時可以被忽略。例如，若一個演算法的時間複雜度為n-2，則當n相當大時(趨近於無窮大時)，此演算法的時間複雜度趨近於n(屬於線性(一次方)量級)；若一個演算法的時間複雜度為35n2+12n+11，則當n相當大時(趨近於無窮大時)，此演算法的時間複雜度趨近於n2(屬於平方量級)；而若一個演算法的時間複雜度為28n3+1245n2+162n+321，則當n相當大時(趨近於無窮大時)，此演算法的時間複雜度趨近於n3(屬於立方量級)。我們通常使用大O記號(Big-O notation)的趨近記號來表示這種趨近情形，我們可以說，大O記號是一個用來表示演算法時間複雜度量級(order)的記號，我們可以將時間複雜度與大O記號的關係整理如下：
一般而言，若是一個演算法的時間複雜度表示為一個多項式，則我們取這個多項式的最高次方為其時間複雜度的量度(order)，並且將此量度以大O記號表示。
以下我們正式定義大O記號：
[定義] Big-O: (O 代表order之意)
令f(n)與g(n)是由非負整數對應至實數的函數，若存在正實數常數c>0和正整數常數n0使得對所有的nn0而言，f(n)cg(n)成立，則我們說f(n)=O(g(n))。(唸作 「f(n)是屬於Big-O of g(n)」，比較正式的英文唸法為「f of n is of Big-O of g of n」)。
例如，存在c=58和n0=1，使得當nn0=1時，35n2+12n+11cn2=(58n2)成立，因此，我們說35n2+12n+11=O(n2)。
時間複雜度 以大O記號表示 量級
162 O(1) 常數(constant)量級
63log n+4 O(log n) 次線性(對數)(sub-linear, logarithmic)量級
37 +52
O( )
平方根(square root)量級
n-2 O(n) 線性(linear)量級
156n+81 O(n) 線性(linear)量級
35n2+12n+11 O(n2) 平方(quadratic)量級
28n3+1245n2+162n+321 O(n3) 立方(cubic)量級
142n+457n3+248n2-45n+81 O(2n) 指數(exponential)量級
表1-1. 時間複雜度的大O記號及其量級。
log n
n n log n n2 n3 2n
0 1.00 1 0 1 1 2
1 1.41 2 2 4 8 4
2 2.00 4 8 16 64 16
3 2.83 8 24 64 512 256
4 4.00 16 64 256 4,096 65,536
5 5.66 32 160 1,024 32,768 4,294,967,296
表1-2.演算法各種時間複雜度的對照數值。
表1-1列出一些以大O記號表示的時間複雜度及其量級，而表1-2、圖1-2與圖1-3則顯示演算法時間複雜度在各種不同量級之下的比較，我們可以發現，某些量級在演算法的資料範圍(問題大小，problem size)還不是很大的情況之下，演算法的時間複雜度的對照數值(執行時間，execution time)就已經是相當大的值了，這表示演算法需要執行相多的執行步驟，當然也就是要執行相當久的時間。因此，如何設計一個時間複雜度量級較低的演算法一直是我們必須擺在心中的一個重要目標。以下是演算法時間複雜度量級高低的次序(靠左邊的量級是比較低的量級)：
O(1)， O(log n)， O( )， O(n)， O(n log n)， O(n2)， O(n3)， O(2n)
以下，我們再舉檢查一個正整數是否為質數的演算法為例，來看看演算法的量級對執行時間的影響。我們先看以下的定理，若我們能善加利用它，則我們可以很容易的設計出一個量級更低的演算法。
[定理]
對於任意的大於2的整數n而言，若所有小於或等於 的整數(1除外)都無法整除n，則 n是一個質數。(在此我們不討論定理的證明)
每個數的因數都是成對出現的，例如，16的因數為1與16(1*16=16)、2與8(2*8=16)、4與4(4*4=16)。成對出現的因數中，一個會小於等於該數的平方根，而另一個則是大於等於該數的平方根，因此，我們只要檢查小於等於該數的平方根的整數中是否有其因數就可以知道該數是不是整數了。
我們根據上列定理設計出一個屬於平方根量級的演算法 演算法Prime2：
Algorithm Prime2(n):
Input:一個大於2的正整數n
Output:true或false(表示n是質數或不是質數)
for i=2 to do
if (n%i)=0 return false
return true
我們可以很輕易的推導出，演算法Prime2的最差狀況(worst case)時間複雜度為 -1=O( )(屬於平方根量級)。而演算法Prime2與演算法Prime1一樣，二者的最佳狀況(best case)時間複雜度都是1=O(1)( 屬於常數量級)。由圖1-1中我們可以看出，平方根量級的演算法Prime2的執行速度將比線性量級的演算法Prime1的執行速度快很多。例如，若輸入的n為2147483647，則演算法Prime1需要執行2147483645次整數除法求餘數和整數比較敘述才可以得知2147483647是質數，而演算法Prime2只要執行 -1=46339次整數除法求餘數和整數比較敘述就可以得知2147483647是質數了。二個演算法的執行時間差距約為46340倍，當然，當所輸入的n越大時，這種差距越大。我們將演算法Prime1和演算法Prime2以Java語言來表示，並再其中插入測量執行時間相關指令來比較二個演算法實際的執行時間。當輸入的整數n為2147483647時，演算法Prime1需要執行131710毫秒(約2.1分鐘)，而演算法Prime2則僅需要不到1毫秒(因此執行結果顯示0毫秒)。二個演算法的執行時間差距超過46340倍。從這二個演算法的執行情形，我們可以明確的看出演算法的好壞對執行時間的影響。
範例程式(檔名：Prime1AP.java)
1: //檔名:Prime1Ap.java
2: //說明:此程式可輸入一個大於2的整數，並判斷此整數是否為質數(prime number)
3: import javax.swing.JOptionPane;
4: public class Prime1Ap {
5: public static void main(String[] 參數){
6: int 整數n;
7: String 輸入字串,顯示字串;
8: 輸入字串=JOptionPane.showInputDialog("請輸入大於2的整數n？");
9: 整數n=Integer.parseInt(輸入字串);
10: boolean 是質數;
11: long 演算法執行前時間=System.currentTimeMillis();
12: 是質數=Prime1(整數n);
13: long 演算法執行後時間=System.currentTimeMillis();
14: long 演算法執行時間=演算法執行後時間-演算法執行前時間;
15: if(是質數) 顯示字串=整數n+"是質數";
16: else 顯示字串=整數n+"不是質數";
17: 顯示字串+=("\n演算法執行時間為"+演算法執行時間+"毫秒(milli-seconds)");
18: JOptionPane.showMessageDialog(null,顯示字串);
19: System.exit(0);
20: } //方法:main() 定義區塊結束
21: static boolean Prime1(int n) {
22: for (int i=2;i<=n-1;++i)
23: if (n%i==0) return false;
24: return true;
25: }
26: } //類別:Prime1Ap 定義區塊結束
執行結果(命令視窗指令：java Prime1AP)
範例程式1-2.質數檢查演算法1執行程式。
範例程式(檔名：Prime2AP.java)
1: //檔名:Prime2Ap.java
2: //說明:此程式可輸入一個大於2的整數，並判斷此整數是否為質數(prime number)
3: import javax.swing.JOptionPane;
4: public class Prime2Ap {
5: public static void main(String[] 參數){
6: int 整數n;
7: String 輸入字串,顯示字串;
8: 輸入字串=JOptionPane.showInputDialog("請輸入大於2的整數n？");
9: 整數n=Integer.parseInt(輸入字串);
10: boolean 是質數;
11: long 演算法執行前時間=System.currentTimeMillis();
12: 是質數=Prime2(整數n);
13: long 演算法執行後時間=System.currentTimeMillis();
14: long 演算法執行時間=演算法執行後時間-演算法執行前時間;
15: if(是質數) 顯示字串=整數n+"是質數";
16: else 顯示字串=整數n+"不是質數";
17: 顯示字串+=("\n演算法執行時間為"+演算法執行時間+"毫秒(milli-seconds)");
18: JOptionPane.showMessageDialog(null,顯示字串);
19: System.exit(0);
20: } //方法:main() 定義區塊結束
21: static boolean Prime2(int n) {
22: for (int i=2;i<=Math.sqrt(n);++i)
23: if (n%i==0) return false;
24: return true;
25: }
26: } //類別:Prime2Ap 定義區塊結束
執行結果(命令視窗指令：java Prime2AP)
範例程式1-3.質數檢查演算法2執行程式。
習題
一、 資料結構的定義為何？演算法的定義為何？為何資料結構語演算法經常一併被提及？
二、 設計一個時間複雜度為O( )的演算法，求一個正整數n有多少個因數。以虛擬碼表示你的演算法，並說明為何其時間複雜度為O( )？
三、 設計一個最差時間複雜度為O( )的演算法，求一個正整數n不等於本身的最大因數。以虛擬碼表示你的演算法，並說明為何其最差時間複雜度為O( )？
四、 設計一個演算法，求一個正整數n不等於本身的最大因數。以虛擬碼表示你的演算法，並求其最差時間複雜度與最佳時間複雜度？(最佳時間複雜度可以為O(1)而最差時間複雜度可以為O( ))
五、 設計一個演算法，求一個正整數n所有因數的總合。以虛擬碼表示你的演算法，並求其時間複雜度？
六、 設計一個演算法，求一個正整數n是否為完美數(perfect number)。以虛擬碼表示你的演算法，並求其時間複雜度？
註：一個整數被稱為完美數(perfect number)若它等於除了它自身之外所有因數的和。例如，1+2+3=6，因此6為perfect number；而1+2+48，因此8不是perfect number。
七、 設計一個演算法，求小於正整數n的所有完美數(perfect number)。以虛擬碼表示你的演算法，並求其時間複雜度？
註：一個整數被稱為完美數(perfect number)若它等於除了它自身之外所有因數的和。例如，1+2+3=6，因此6為perfect number；而1+2+48，因此8不是perfect number。
八、 設計一個演算法，求一個正整數m與一個正整數n是否互質。以虛擬碼表示你的演算法，並將之轉換為Java語言程式碼？
九、 以大O記號寫出下列函數？
(1) (2)
十、 試決定下列片斷程式中的指令x←x+1的執行次數？ (87年資料處理高考)
(1)for i←1 to n do
for j←1 to n do
x←x+1
end
end
(2)for i←1 to n do
for j←i to n do
for k←j to n do
x←x+1
end
end
end
(3)for i←1 to n do
j←i
for k←j+1 to n do
x←x+1
end
end
(4)k←100000
while k5 do
k←k div 10
x←x+1
end
十一、 若一個程式執行的時間是1000n2+n log n2，則相當於：(A).O(n2) (B).O(n log n) (C).O(n3) (D). O(n2n log n2)。 (88年普考)
十二、 證明 =O(n2)。
|
|
發表於 2012-7-8 20:40:09
