Chapter 1 Chang Chi-Chung 2011.09.22.

Presentation on theme: "Chapter 1 Chang Chi-Chung 2011.09.22."— Presentation transcript:

1 Chapter 1 Chang Chi-Chung

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

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

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

5 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

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

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

8 演算法的計數分析(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

9 演算法的計數分析(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) other

10 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;

11 Asymptotic Notation(O, , )

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

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

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

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

16 證明 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) 得證

17 Show that 10n2+9 = O(n2) By Big-O definition 本題只要找出 c 與 n0 即可得證
f (n) = O(g(n)) 若且唯若存在有 c＞0 和 n 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) 得證

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

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

20 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 …….

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

22 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;

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

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

25 為什麼這樣分析？(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 秒

26 範例：計算向量內積 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

27 範例：底下計算矩陣加法 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

28 範例：底下計算矩陣乘法 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

29 測驗題：底下的程式需要多少時間？ 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

30 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

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

32 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)

33 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)

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

35 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 ) 

36 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);

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

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

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

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