Chapter 1 Chang Chi-Chung 2011.09.22

What’s Algorithm 演算法是由一序列的指令所組成。依序執行這些指令可以解決給定的問題。演算法具有下列五大條件： 輸入(Input) 外界可提供零個或多個輸入資料。 輸出(Output) 必須最少有一個輸出的結果。 明確性(Definiteness) 每一個指令的功能都必須明確而不混淆。 有限性(Finiteness) 對任意的輸入資料，演算法必須在有限的時間內執行完成。 有效性（Effectiveness) 每一個指令必須非常基本：僅用紙筆即可完成。

演算法的表示方法 Natural language Graphic representation Pseudo language Chinese、English Graphic representation Flow Chart Pseudo language

演算法分析方法 實驗分析 漸進分析 攤銷分析 Time Complexity Space Complexity

Example: 虛擬碼 Algorithm arrayMax(A, n) Input: An array A storing n>=1 integers Output: The maximun element in A currentMax  A[0] for i 1 to n - 1 do if currentMax < A[i] then currentMax  A[i] return currentMax

虛擬碼 循序 重複 選擇 運算式 「」 method 宣告：Algorithm 函數名(參數1, 參數2..) 陣列索引 A[i] return 值 重複 while 條件 do 動作 repeat 動作 until 條件 for 變數增值定義 do 動作 選擇 if 條件 then 為真的動作 [else 為假的動作]

隨機存取機器模型 Random Access Machine 電腦 = CPU + 記憶單元 CPU 可以隨意存取記憶單元 執行基本運算僅需常數個步驟(常數時間) 基本運算 變數值設定、陣列索引、物件參考 呼叫method、從method返回 比較、算術運算

演算法的計數分析(1) 2 5n 1 + n 2 n-1 2 7n-2 2 1 Algorithm arrayMax(A, n) Input: An array A storing n>=1 integers Output: The maximun element in A currentMax  A[0] for i 1 to n - 1 do if currentMax < A[i] then currentMax  A[i] return currentMax 2 5n 7n-2 至 1 + n 2 n-1 2 2 1

演算法的計數分析(2) if n=1 T(n-1) + 7 other T(n) = Algorithm recursiveMax(A, n) Input: An array A storing n>=1 integers Output: The maximun element in A if n = 1 then return A[0] return max { recursiveMax(A, n-1), A[n-1]} T(n) = if n=1 T(n-1) + 7 other

An Exercise Algorithm Sum(A, n) sum  0; for i  0 to n-1 do Input: An array A storing n>=1 integers Output: Sum of the array A sum  0; for i  0 to n-1 do sum  sum + A[i]; return sum;

Asymptotic Notation(O, , )

最差狀況分析（worst-case analysis） 分析演算法在所有可能的輸入組合下，最多所需要的時間。 最佳狀況分析（best-case analysis） 分析演算法在所有可能的輸入組合下，最少所需要的時間。 平均狀況分析（average-case analysis） 分析演算法在所有可能的輸入組合下，平均所需要的時間。

Big-O f (n) = O(g(n)) 如果存在正數 c 和 n0 使得對所有的 n, n >= n0, f (n) <= c．g(n) 。 n n0

Big- f (n) = Q (g(n)) 如果存在正數 c1, c2 和 n0 使得對所有的 n, n >= n0, c1．g(n) <= f (n) <= c2． g(n) 。 n n0

Big- f (n) = (g(n)) 如果存在正數 c 和 n0 使得對所有的 n, n >= n0, f (n) >= c．g(n) 。 n n0

證明 7n-2 是 O(n) By Big-O definition f (n) = O(g(n)) 若且唯若存在有 c＞0 和 n0 N, 對所有的 n, n≧n0 使得 f (n) ≦ c．g(n) 。 本題只要找出 c 與 n0 即可得證 取 c = 7 且 n0 = 1 ，則對所有的 n, n≧1 會使得 7n-2 ≦ 7．g(n) = 7n 即 7n-2 = O(n) 得證

Show that 10n2+9 = O(n2) By Big-O definition 本題只要找出 c 與 n0 即可得證 f (n) = O(g(n)) 若且唯若存在有 c＞0 和 n0 N, 對所有的 n, n≧n0 使得 f (n) ≦ c．g(n) 。 本題只要找出 c 與 n0 即可得證 取 c = 11 且 n0 = 3 ，則對所有的 n, n≧3 會使得 10n2 + 9 ≦ 11．g(n) = 11n2 即 10n2+9 = O(n2) 得證

定理 請參看課本 P15 定理 1.7 若 則 若 則 若 若且唯若 若 則

Exercises 證明 2n3 + 4n2log n 是 O(n3) 證明 3log n + log log n 是 (log n)

Order the Time Complexity O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) 1 2 3 4 5 8 16 32 24 64 160 256 1024 512 4096 32,768 65,536 4,294,967,296 40,320 20,922,789,888,000 …….

Asymptotic Notation 函數: ω Ω Θ O o 實數: >  =  < 實數: >  =  < 任兩實數皆可互相比較大小，但是任兩函數並不一定能夠互相比較。 f(n)=n 和 g(n)=n1+sin n

Example O(1) O(n) O(1) O(n) O(n) prime ( int n ) { int k; if (n <= 1) return false; k = 2; while ( k < n ) { if ( n % k == 0 ) k++; } return true;

演算法分析技巧 在迴路之外的指令所需的時間為 O(1)，而且通常可以忽略不計。 從上面的分析過程中，我們可以得到下面的規則： 在迴路之外的指令所需的時間為 O(1)，而且通常可以忽略不計。 迴路所需的時間為其執行的次數（以 big O 符號表之）。迴路中的指令，若不是另一個迴路，則可以忽略。 若迴路執行的次數與 input size 無關，則其所需的時間仍為O(1)。 若程式中含有兩段的迴路，則只需要考慮執行次數較多的迴路即可。

為什麼這樣分析？(1) 不同的演算法在解決相同問題時在效率上可能會有相當的差異。這個差異可能遠比硬體或軟體所造成的影響還要巨大。 Example 將 n 個數字由小排到大 insertion sort 約需 c1n2 merge sort 約需 c2 nlogn 一般而言，c1 < c2

為什麼這樣分析？(2) 例如：c1=2，c2=50，電腦 A 每秒鐘可跑 109 個指令，電腦 B 較慢，每秒鐘只能跑 107 個指令。 假設 n=106： 在電腦 A 上跑 insertion sort 的時間為 2 · (106)2 個指令 109 指令/秒 在電腦 B 上跑 merge sort 的時間為 50 · 106 lg 106 個指令 107 指令/秒 = 2000 秒 ≒ 100 秒

範例：計算向量內積 n 需要 O(n) 時間。 int inner_product (int u[], int v[], int n) { int i, sum = 0; for (i = 0; i < n; i++) sum += u[i]*v[i]; return sum; } n

範例：底下計算矩陣加法 n n 的演算法需要 O(n2) 時間。 for (i = 0; i < n; i++) for (j = 0; j < n; j++) c[i][j] = a[i][j] + b[i][j]; n n

範例：底下計算矩陣乘法 n n n 的演算法需要 O(n3) 時間。 for (i = 0; i < n; i++) for (j = 0; j < n; j++) { sum = 0; for (k = 0; k < n; k++) sum += a[i][k] * b[k][j]; c[I][j] = sum; } n n n

測驗題：底下的程式需要多少時間？ for (i = 0; i < n; i++) for (j = i+1; j < n; j++) { } n n - i - 1 for (i = 0; i < n; i++) for (j = i+1; j < 100; j++) { } n 100 for (i = 0; i < n; i++) { } for (i = 0; i < n; i++) for (j = 0; j < n; j++) { n n n

Recursive Algorithm Direct Recursive Indirect Recursive The functions call themselves before they is done. （函數自己呼叫自己） Indirect Recursive The functions call other functions that again invoke the calling function. Example: function A  function B  function A

Recursive Programming Style Function recursive() { if (終止條件判斷式) //成立，終止遞迴 return; else (遞迴呼叫方式); }

Recursive Example – 求 n! iterative version recursive version int factor(int n) { int result=1; for (int i=n;i>=1;i--) result *= i; } return result; recursive version int factor(int n) { if (n==1) return 1; else return n*factor(n-1); } O(n) O(n)

Performance Analysis recursive version 每次遞迴需 2 steps 1 int factor(int n) 2 { 3 if (n==1) 4 return 1; 5 else 6 return n*factor(n-1); 7 } 每次遞迴需 2 steps line 3 與 line 6 T(1) =2 (line 3 與 line 4) Recursive Formula T(n) = T(n-1) + 2 = T(n-2) + 4 = ... = T(1) + 2*(n-1) = 2n O(n)

Recursive Example: HANOI Towers 將 A 柱上所有的碟子搬移到 B 柱 搬移的過程小碟始終要在大碟之上。 相傳印度恆河的僧侶只要將 A 柱上的 64 個碟子全部搬移到 B 柱，世界末日就來到。如果他們一秒鐘可搬移一個碟子，問世界末日何時來到？ C A B

Recursive Example: HANOI Towers 3 2 1 C A B 以上圖為例，要搬移 A 柱上的三個碟子到 B 柱，我們可以簡單的這樣想： 先將最上面二個小碟 (1-2) 搬到 C 柱。( recursive, n-1 ) 將留在 A 柱的大碟搬到 B 柱。 最後，再將 C 柱上的二個小碟 (1-2) 搬到 B 柱。 ( recursive n-1 ) 

Recursive Example: HANOI Towers //n is amount of disks, source, dest, temp are towers. void tower(int n, char source, char dest, char temp) { static int step; if (n==1) step++; cout << "Step " << step << ": desk " << n << " from " << source << " move to " << dest << endl; } else tower(n-1, source, temp, dest); tower(n-1, temp, dest, source);

Performance Analysis 若有 n 個 disks，問最少要搬動多少次？ 移動一次需一秒，問 64 個 disks 需幾秒？ 由上述程式，我們可以得到遞迴方程式  T(n) = 2T(n-1)+1 = 2[ 2T(n-2)+1 ] + 1 = 22 T(n-2) + 2 +1 = 22[ 2T(n-3)+1 ] + 2 + 1 = 23T(n-3) + 22+ 2+ 1 = …… = 2n-1 T(1) + 2n-2 + 2n-3 + …. + 2 + 1 = 2n-1 + 2n-2 + …. + 2 + 1  (等比級數，公比=2，有n 項) = 2n – 1 移動一次需一秒，問 64 個 disks 需幾秒？ 令 10n = 264 (兩邊同取 log) n = 64 * log 2 = 64 * 0.3010 = 19.264 ≒ 20 故約需 1020 秒，約等於 3*1012 年 由此可知，世界末日還早，還有很多時間研究資料結構 

應用演算法的重要觀念 asymptotic 式的演算法分析技巧 ，雖可提供我們評判演算法的優劣，但是在實際運用上必須進一步分析。比方說：演算法 A 需要 103n 的步驟、演算法 B 需要 n2 的步驟。分析的結果演算法 A 是 O(n) 而演算法 B 是 O(n2)，但這並不是說演算法 A 一定比演算法 B 好 — 當 n 不大於103 的時候，演算法 B 就比演算法 A 有效率，因此在這個情形下，我們應該選擇演算法 B 而不是演算法 A。 換句話說，在選擇演算法時，除了考慮其 order 外，也必須考慮所處理問題的大小（即 n ）。

作業1 問題 給定一行文字，請你幫忙列出 ASCII 字元的出現頻率。你可以假設 ASCII 前 32 個字元以及後 128 個字元不會出現。每一行文字的後面可能會以 ’\n’ 和 ’\r’ 結束，但是不用把那些字元考慮進去。 輸入 會給好幾行文字。每一行的長度最大會到 1000。 輸入以 檔案結尾為結束。 輸出 對於每一行輸入，根據出現的頻率高低印出 ASCII 字元的 ASCII 值以及該字元出現的頻率(頻率高的先印)。在每組輸出之間要印一個空行。如果兩個 ASCII 字元有相同的頻率，那麼 ASCII 值比較小的優先印出。

以下是一個輸出入的實例: Sample Input Sample Output AAABBC 122333 67 1 66 2 65 3 49 1 50 2 51 3