Week 2: 程式設計概念與 演算法的效能評估

Presentation on theme: "Week 2: 程式設計概念與 演算法的效能評估"— Presentation transcript:

1 Week 2: 程式設計概念與 演算法的效能評估

2 學習目標 能說出好程式的條件 能寫出結構化程式主要的三個流程結構 能描述兩大類評估演算法效能的方式
能以三種時間複雜度的表示法評估一個演算法的執行次數 能判斷不同等級的時間複雜度之順序

3 程式設計的概念 程式是資料結構與演算法的實作 程式設計的步驟 Step 1: 分析所要解決的問題 Step 2: 設計解題的步驟 (演算法)
了解需求，確定輸入與輸出資料 Step 2: 設計解題的步驟 (演算法) 使用文字敘述、流程圖或虛擬碼來表示 Step 3: 撰寫程式 Step 4: 上機測試、偵測錯誤 Step 5: 編寫程式說明書

4 演算法和程式的差異 「演算法」是以「人」為主，亦即「任何人都可以閱讀的程式碼」，因此，必須特別強調「可讀性」
以流程圖或虛擬碼來說明 「程式」則是以「電腦」為主，它強調程式的執行結果正確性、可維護性及執行效率

5 為什麼要撰寫程式 我們為什麼要花那麼多時間來撰寫程式呢？ 主要目的：它可以快速解決「複雜的問題」

6 好程式的條件 正確性(Correctness) 效率性(Performance) 可維護性(Maintainable) 基本要求
以頻率計數(Frequency Count)來計算程式被執行的次數，評估程式的效率，例如: 可維護性(Maintainable) 程式設計方法和風格—結構化程式設計、縮排、註解、變數命名、程式說明書等等

7 結構化程式設計 結構化程式設計由Dijkstra (1969)提出： 利用「由上而下」的技巧，將程式分解成多個具有獨立功能的模組
1. 消除程式因goto而造成如麵條式的混亂狀態 2. 強調任何程式邏輯均可由三種結構組成 利用「由上而下」的技巧，將程式分解成多個具有獨立功能的模組 主系統 獨立功能 模組1 獨立功能 模組2 獨立功能 模組3

8 三個基本結構 循序(Sequence)：簡單命令式的指令如 COMPUTE, READ, WRITE 與代數指令如X=Y+Z
選擇(Condition)：需做決策時，用 IF-THEN-ELSE 指令與CASE 指令 重複(Repetition)：當需反覆時，用 DO-WHILE 與DO-UNTIL 指令

9 循序結構 程式由上而下逐一執行 最基本的結構 開始 敘述1 敘述2 ............ 敘述n 結束
import java.io.*; public class test { public static void main(String[] args) float Average=0; int score1=60,score2=70; Average = (float)(score1+score2)/2 ; System.out.println("平均：" + Average); } 敘述2 敘述n 結束

10 選擇結構 又可稱為決策結構，在某種條件成立時才執行某些敘述，不成立時則執行另一種敘述 import java.io.*;
public class test { public static void main(String[] args) int score=80; if (score<60) System.out.printf(“不及格”); else System.out.printf(“及格”); } True 條件式 False 敘述1 敘述2

11 重複結構 讓某一段程式反覆執行多次的敘述的結構，稱為「迴圈結構」或「重複結構」 例如: for 迴圈結構 i=1
import java.io.*; public class test { public static void main(String[] args) int sum=0; for (int i=1; i<=100; i++) sum+=i; } i<=100 False True sum+=i i++

12 重複結構 (續) 讓某一段程式反覆執行多次的敘述的結構，稱為「迴圈結構」或「重複結構」 例如: while 迴圈結構 i=1
import java.io.*; public class test { public static void main(String[] args) int sum=0, i=1; while (i<=100) { sum+=i; i++; } }} i<=100 False True sum+=i i++

13 演算法的效能評估 用來計算某些演算法所撰寫的程式，在經過編譯之後實際執行所需要的時間
但是，實務上有可能因為程式編譯的過程或是電腦設備的差異使得效率分析會因電腦的軟硬體不同而有不同的結果 因此，效能的評估方式可分為兩大類： 空間複雜度（Space Complexity） 時間複雜度（Time Complexity）

14 空間複雜度 指從呼叫程式開始到完成之過程，所佔用的記憶體空間
例如：變數宣告、函數呼叫、參數傳遞等 由於記憶體和儲存媒體愈來愈大，也愈來愈便宜，程式執行所需空間比較不是問題，因此，時間複雜度比空間複雜度來得重要 通常評估程式或演算法的效率，較常以時間複雜度來評估

15 時間複雜度 指程式開始執行到結束所花費的時間 影響程式執行時間的因素 演算法的優劣 電腦的執行速度（CPU速度）
執行時間 = 執行次數 × 每次執行所需時間 執行每一行程式所需時間必須考慮到電腦CPU執行速度及編譯器的功能，在評估上比較不客觀。因此，通常只考慮執行的次數，執行次數的多寡，往往是用來決定演算法效率的好壞。

16 如何計算程式執行次數? 計算程式的執行次數，亦可稱為頻率計數(Frequency Count)指每一行程式的執行次數，或者更精確一點說，是每一個敘述的執行次數，兩者皆有學者採用 public sum() { int s=0; for (int i=1; i<=100; i++) s+=i; } 執行次數 頻率計數 1次 1次 101次 次 100次 100次 202次 303次 本教材使用頻率計數

17 頻率計數的計算規則 只計算可執行的程式碼 同一個運算式只算一次 未指定初值的變數宣告不算 註解不算 程式區塊的左右大括號 { 和 } 都不算
例如: a=a+1雖然有兩個運算(=和+)，但只算一次 未指定初值的變數宣告不算 註解不算 程式區塊的左右大括號 { 和 } 都不算

18 舉例1 例如：下列程式的頻率計數為多少? 1次 2次 3次 4次 //這是一個測試程式 int a=4, b=6, c; c=a+b;
<PowerClick><Answer>3</Answer><Option>4</Option><Point>1</Point></PowerClick>

19 舉例2 假設一個運算所花費的時間為一個單位時間，分析下面程式的執行時間 int s=0; 1
for (int i=1; i<=100; i++) s+=i; System.out.println(“s=“+s); 1 100 1 共需 304 單位時間

20 分析程式時，資料量通常以無線大的情形來考慮，即n值很大時
舉例3 假設一個運算所花費的時間為一個單位時間，分析下面程式的執行時間 int s=0, n; for (int i=1; i<=n; i++) s+=i; System.out.println(“s=“+s); 1 1+(n+1)+n n 1 分析程式時，資料量通常以無線大的情形來考慮，即n值很大時 共需 3n+4 單位時間

21 舉例4 假設一個運算所花費的時間為一個單位時間，分析下面程式的執行時間 for (int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) { System.out.println(i*j); } 1+(n+1)+n n×(1+(n+1)+n) n×n×1 共需 3n2+4n+1 單位時間 通常會定義執行時間為一個函式T(n) T(n) = 3n2+4n+1

22 時間複雜度的概算 雖然評估演算法愈精準愈好，但耗費很大功夫計算真正的執行次數是沒有意義的，因此我們常使用「概量」(漸進式表示法)來衡量
三種時間複雜度概量表示法 O (Big-O)…以最多時間來概算(上限) Ω(Omega)…以最少時間來概算(下限) Θ(Theta)…以恰好時間來概算(同時為上限和下限) 最常使用

23 時間複雜度: O (Big-O) Big-O可視為時間複雜度的最壞表現，或稱為理論上限(Upper bound)
定義：某程式的執行時間為T(n) ，若存在兩個常數c和n0，當n≧n0時，使得T(n)≦cf(n) ，則此程式的時間複雜度是O(f(n))

24 時間複雜度: O (Big-O) 例如：請證明T(n)=4n2+174 的時間複雜度可用O(n2)表示 ∵ 欲證明 T(n)=O(n2)
∴ f(n)=n2 預找到某 c 使得T(n)≦cf(n) 亦即 4n2+174 ≦ c * n2 ∴ (c-4) n2 ≧ 174 ∴ 我們可找到 c=5 時，n2 ≧174，對所有n > n0 = 14 使得 4n2+174 ≦ 5 * n2，所以 T(n)= O(n2)

25 時間複雜度: O (Big-O) 原理說明 假設某一演算法的估算時間函式T(n)=4n2+174，則我們預估其時間複雜度為O(n2) ，亦即f(n)=n2 當n ≧14 (=n0) 之後，5×f(n) 一定會大於或等於T(n)，所以O(n2)足以代表4n2+174 <Operate>

26 時間複雜度: O (Big-O) 例如：下列程式的時間複雜度Big-O為何? for (int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) { System.out.println(i*j); } 1+(n+1)+n n+n×(n+1)+n×n n×n 共需 3n2+4n+1 單位時間 ‖ T(n) 想想看： 假設f(n)=n2，我們是否能找到適當的常數c和n0，使得n≧n0且T(n)≦cf(n)？ 我們可找到c=8, n0=1，使T(n)≦cf(n) ，故其時間複雜度Big-O為 O(n2)

27 時間複雜度: O (Big-O) 簡易規則：取執行時間函數T(n)中指數最高的項目，並移除係數即可
for (int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { System.out.println(i*j); } 1+(n+1)+n n×(1+(n+1)+n) n×n×1 共需 3n2+4n+1 單位時間 T(n)= 3n2+4n+1 ，取指數最高項3n2，並移除係數得 n2，因此，此程式的時間複雜度Big-O為 O(n2)

28 指數時間(exponential time)
常見的 Big-O 函式 如何比較兩個程式的效率哪一個好？ 將兩個程式皆以 Big-O 函式表示其時間複雜度，再進行比較 常見的Bio-O函式如右： O(1) 常數時間 (constant time) O(n) 線性時間 (linear time) O(log2n) 次線性時間 (sub-linear time) O(nlog2n) 線性乘對數時間 O(n2) 平方時間(quadratic time) O(n3) 立方時間 (cubic time) O(2n) 指數時間(exponential time) best worst

29 常見 Big-O 函式效能比較

30 練習 請使用Big-O表示下列時間函數的時間複雜度 T(n) = 4n+12 T(n) = 10n+25 T(n) = 8n2+11n+18

31 解答 T(n) = 4n+12 = O(n)，因為存在 c=5，n0=12，使得n ≧ 12後，4n+12 ≦ 5n（或 c=6，n0=6，使得n ≧ 6後，4n+12 ≦ 6n） T(n) = 10n+25 = O(n)，因為存在c=11，n0=13，使得n ≧ 13後，10n+25 ≦ 11n； T(n) = 8n2+11n+18 = O(n2)，因為存在c=9，n0=13，使得n ≧ 13後，8n2+11n+18 ≦ 9n2 T(n) = 6×2n+n2 = O(2n)，因為存在c=7，n0=4，使得n ≧ 4後，6×2n+n2 ≦ 7×2n

32 解答(續) T(n) = 326 = O(1)，因為存在 c=327，n0可任取，使得n ≧ n0後，326 ≦ 327×1；
T(n) = 9n2+n+11 = O(n)，因為找不到適當的 c 和 n0，使得n ≧ n0後，9n2+11 ≦ cn； T(n) = 100n3 = O(n4)，因為存在c=16，n0=8，使得 n ≧ 8後，100n3 ≦ 16n4

33 時間複雜度: Ω (Omega) Omega(Ω)可視為時間複雜度的最佳表現，或稱為理論下限(Lower bound)
定義：某程式的執行時間為T(n) ，若存在兩個常數 c 和 n0，當n≧n0時，使得T(n)≧cf(n) ，則此程式的時間複雜度是Ω(f(n)) 通常Big-O用來討論演算法的時間複雜度，而Ω則是用來討論演算法的難易度

34 時間複雜度: Ω (Omega) 例 1：證明 T(n)=3n+2 ，可以用Ω(n)來表示 已知 f(n) = n
欲證明 T(n) ≧ c*f(n) 亦即 3n+2 ≧ c * n ∴ (3-c) * n ≧ -2 ∴ 當 c = 3，n0=1 時上式可成立 亦即c = 3，n0=1 時 T(n)= Ω(n)

35 時間複雜度: Ω (Omega) 例 2：某程式的執行所花費的時間函數T(n)=6n2+3n+2，請利用Ω來表示T(n)的時間複雜度
∴ 6n2+3n+2 ≧ c * n2 ∴ (6-c) n2+3n+2 ≧ 0 ∴ 存在 c=6 ，對所有的 n ≧ 1 ， 使得 6n2+3n+2 ≧ 6n2， 所以 f(n)= Ω(n2)

36 練習(Ω) 請用Ω表示下列時間函式 T(n) = 4n+12 T(n) = 10n+25 T(n) = 8n2+11n+18

37 解答 4n+12=Ω(n)，因為存在c=1，n0=1，使得n1後，4n+12  n
8n2+11n+18=Ω(n2)，因為存在c=1，n0=1，使得n1後，8n2+11n+18  n2 6×2n+n2=Ω(2n)，因為存在c=1，n0=1，使得n1後，6×2n+n2  1×2n

38 時間複雜度: Theta (Θ) Theta (Θ)可視為時間複雜度的平均表現，既是上限，也是下限
定義：某程式的執行時間為T(n) ，若存大於0的正常數c1、c2和n0，讓所有n值在n≧n0時，使得c1f(n)≦T(n)≦c2f(n)，則此程式的時間複雜度是Θ(f(n)) 即 f(n) 既是 T(n) 的上限，也是下限，是 T(n) 的最佳解 (Optimal solution)

39 時間複雜度: Theta (Θ) 例1：證明 T(n) = 3n+2 ，可以用Θ(n)表示 已知 f(n) = n
欲求 c1f(n)≦T(n)≦c2f(n) 亦即 c1n ≦ 3n+2 ≦ c2n 存在 c1=3，c2=4 當 n ≧ 1 時，滿足3n+2≧3n 當 n ≧ 2 時，滿足3n+2≦4n 結論 3n+2=Θ(n)

40 時間複雜度: Theta (Θ) 例2：證明T(n)=10n2+4n+6，可以用Θ(n2)表示 已知 f(n) = n2
欲求 c1f(n)≦T(n)≦c2f(n) 亦即 c1n2 ≦ 10n2+4n+6 ≦ c2n2 存在 c1=10，c2=11 當 n ≧ 1 時，滿足 10n2+4n+6 ≧10n2 當 n ≧ 6 時，滿足 10n2+4n+6 ≦11n2 結論3n+2=Θ(n2)

41 練習 請用Θ表示下列時間函式 4n+12 8n2+11n+18

42 解答 4n+12 = Θ(n)，因為存在c1=1、c2=5，n0=12，使得n≧12後，1×n ≦ 4n+12 ≦ 5×n
8n2+11n+18 = Θ(n2)，因為存在c1=1、c2=9，n0=13，使得n≧13後，1×n2 ≦ 8n2+11n+18 ≦ 9n2

43 本章節結束