Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order

Presentation on theme: "Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order"— Presentation transcript:

1 Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order

2 ▓ Outlines 本章重點 Algorithm
Def. 與5個性質 Pseudocode The Importance of Developing Efficient Algorithms Analysis of Algorithms Space complexity Time complexity Asymptotic Notation (漸近式表示) Order , , , o,  Using a Limit to Determine Order

3 ▓ Algorithm 通常在針對某一問題開發程式時，都會經過下列步驟： Example: 計算大學入學考試中，某一單科分數之高標
Step 1: 明確定義問題 Step 2: 設計演算法，並評估其執行效率 Step 3: 撰寫程式，並加以測試 Example: 計算大學入學考試中，某一單科分數之高標 明確定義：計算所有考生在該科中前25%成績之平均。 演算法： Step 1: 將所有考生英文成績排序 (由高至低) Step 2: 將排名在前面1/4的成績資料相加後，再除以1/4的人數 撰寫程式：...

4 當我們使用某種技巧解決一個問題時，會產生一種逐步執行的程序(step-by-step procedure)來解決問題，該種逐步執行的程序即稱為解決這個問題的演算法。
Def: 完成特定功能之有限個指令之集合。 需滿足下列5個性質： Input: 外界至少提供0個輸入 Output: Algorithm至少產生1個輸出結果 Definiteness (明確): 每個指令必須是Clear and Unambiguous Finiteness (有限性): Algorithm在執行有限個步驟後，必定終止 Effectiveness (有效性): 用紙跟筆即可追蹤Algorithm中執行的過程及結果

5 Pseudocode (虛擬碼) Note: One of the most common tools for defining algorithms is pseudocode, which is part English, part Structured Code.

6 Example of Pseudocode 問題1: 搜尋問題 範例:

7 問題演算法:

8 No standard for pseudocode
可以寫得很像英文敘述 也可以寫得很像程式語句

9 ▓ 發展有效率演算法的重要性 不管電腦變得多快，記憶體變得多便宜，效率(Efficiency)仍然是設計演算法時最重要的考量.
排序問題 (Sorting problem): 將一組資料以遞增 (increasing) 或以遞減 (decreasing)的順序加以排列. 11, 7, 14, 1, 5, 9, 10 ↓sort 1, 5, 7, 9, 10, 11, 14  欲比較的兩個演算法: Insertion sort (插入排序法): O(n2) Quick sort (快速排序法): O(n log n)

10 兩個演算法所安裝之系統: Quick Sort: IBM PC/XT (1983年產品，以 Intel 8088 CPU為核心 )
Insertion Sort: VAX8800 (DEC超級迷你電腦)

11 ▓ 演算法的分析 若要得知一個演算法解決一個問題有效率的程度，我們必須分析(Analyze)該演算法。
一個Algorithm的好壞，通常有兩個評估因子： Space (空間): Space Complexity 記憶體複雜度 (Memory Complexity) Time (時間): Time Complexity

12 時間複雜度 (Time Complexity)
一般來說，對一個演算法進行時間複雜度分析就是求得： 在每個不同的輸入大小 (the size of the input)之下，該演算法所執行的基本運算次數 (how many times some basic operation is done)。 分析方式： 我們要分析一個演算法的效率，是將該演算法在每個不同的輸入大小 之下，所執行的基本運算次數 設定成一個函數 (Function ; 或稱Time function, Complexity function亦可) T(n)。 T(n) 被定義為在大小為n的輸入範例下，某一個演算法所執行的基本運算次數。(the number of times the algorithm does the basic operation for an instance of size n.)

13 範例  T(n) = 1+2n+1+1 = 2n+3. 每行指令的執行次數 程式 1 n+1 n
不可執行!!∵就系統執行的角度而言，變數宣告只是在Compile時，在M.M.中建立一個空間，但不會產生相對應的執行碼!!除非在宣告的同時有指派一個初始值，指派的動作就會有相對應的執行碼產生以供程式執行時使用。 每行指令的執行次數 程式 1 n+1 n float sum(float list[ ], int n) { int i; float tempsum = 0; for (i=0; i<n; i++) tempsum += list[i]; } return tempsum;  T(n) = 1+2n+1+1 = 2n+3.

14 有許多被設計出來的演算法，當輸入資料的情況不同時，所分析出來的執行次數也有所不同。
因此，在分析這些演算法的執行次數時，可依據輸入資料的不同情況區分成三個Case來加以分析: The worst case (最差情況) 輸入大小為n的情況下，演算法執行基本運算次數的最大值。 W(n): worstcase time complexity The best case (最佳情況) 輸入大小為n的情況下，演算法執行基本運算次數的最小值。 B(n): best-case time complexity The average case (平均情況) 輸入大小為n的情況下，演算法執行基本運算次數的平均值。 A(n): average-case time complexity

15 Worst-case time complexity analysis
例：循序搜尋法 (Sequential Search) 假設一定會搜尋到所要求的item

16 Best-case time complexity analysis
假設一定會搜尋到所要求的item

17 Average-case time complexity analysis
假設一定會搜尋到所要求的item

18 對於上述時間複雜度分析，我們較常進行最差情況與平均情況的分析，而不是最佳情況分析。
平均情況分析是很有用的，這是因為它告訴我們：一個演算法在有許多不同的輸入狀況時，總共所花費的時間為何。 Ex: A sorting algorithm that was used repeatedly to sort all possible inputs. 最差情況分析是很有用的，這是因為它告訴我們：一個演算法執行時間的上限為何。 Ex: A system that monitored a nuclear power plant 相對來說，最佳情況分析的用處實在不大。 通常，平均情況比最差情況要難分析。 (Worst Case最常被討論)

19 T(n) 被稱為所有情況時間複雜度 (Every-case time complexity)，這是因為：
求得 T(n) 的過程稱為所有情況時間複雜度分析 (Every-case time complexity analysis)。

20 ▓ 量級 (Order) 前面所提到之基本運算的執行次數，可利用漸近式符號(或稱量級, Order)予以表示。 主要原因：
有些程式間實際執行次數看似不同，但是在電腦上執行的效能卻差不多。 指令有的簡單，有的複雜。如: 浮點數運算比整數運算難 除法和加法運算的複雜性不同 for i=1 to n do a=(b+c)/d+e; T1=b+c; T2=T1/d; a=T2+e; T(n)=n T(n)=3n 都落到相同的範圍 n

21 一般演算法分析常見的Order 大小排序如下：
將具有不同但近似之執行次數的一些演算法歸納到相同的時間等級之中。 一般演算法分析常見的Order 大小排序如下： 1(或常數) < log n < n < n log n < n2 < n3 < 2n < 3n < (n/2)n/2  n! 1: 表示敘述的基本運算的次數是固定的(constant)， n: 表示敘述運算次數之Order呈線性成長。 n2: 表示敘述運算次數之Order呈二次多項式曲線成長。 n3: 表示敘述運算次數之Order呈三次多項式曲線成長。 課本上的 lg n = log2n

22 Figure 1.3: • Growth rates of some common complexity functions

23 研究演算法是為了正確有效率地解決問題。 尚可接受 需要改進

24 有下列三個代表演算法執行時間的時間函數:
以直覺的方式介紹Order 有下列三個代表演算法執行時間的時間函數: 5n2 5n 0.1n2 + n + 100  可稱這些函數為平方時間(Quadratic term). 某個演算法的時間複雜度在 (n2)中，該演算法就被稱為平方時間演算法 (quadratic-time algorithm)。 通常，一個演算法的複雜度必須為(n lg n)或更好，我們才會認為這個演算法能在可忍受的時間內處理輸入大小非常大的範例。  僅表示某一個演算法分析方式的表示符號 (n2)

25 以嚴謹的方式介紹Order 共有五種漸近式表示方法： Big-O (O) Omega () Theta () Small-O (o)
Small-Omega ()

26 Big-O (O) Upper bound of f(n). Definition:
在一個多項式中，取最大項當成是理論上限，即程式執行時花費時間的成長率。 Definition: f(n) = O(g(n)) if and only if 存在兩正數c和no, 使得f(n) ≤ cg(n), for all n ≥ no. n：輸入資料量大小。 f(n)：在理想狀況下，程式在電腦中的指令實際執行次數。 g(n)：執行時間的成長率。

27 以定義來說明範例 f(n) = 3n+2, 則 f(n) = O(n). f(n) = 5n2+3n+2, 則 f(n) = O(n2).
f(n) = O(n) if and only if 存在兩正數c = 4 和no = 2 , 使得f(n) ≤ cg(n), for all n ≥ no. 先決定c的值，鎖定f(n)中的最大項之值(即: 3n)，c只要比該項的常數值大1即可!!再由c去推no。 3n+2 ≤ 4n  n ≥ 2。 f(n) = 5n2+3n+2, 則 f(n) = O(n2). f(n) = O(n2) if and only if 存在兩正數c = 6 和no = 4 , 使得f(n) ≤ cg(n), for all n ≥ no. 先決定c的值，鎖定f(n)中的最大項之值(即: 5n2)，c只要比該項的常數值大1即可!!再由c去推no。 5n2+3n+2 ≤ 6n2  3n+2 ≤ n2  取 no = 4。

28 Omega () Lower bound of f(n). Definition:
f(n) = (g(n)) if and only if 存在兩正數c和no, 使得f(n) ≥ cg(n), for all n ≥ no.

29 以定義來說明範例 f(n) = 3n+2, 則 f(n) = (n). f(n) = 5n2+3n-2, 則 f(n) = (n2).
f(n) = (n) if and only if 存在兩正數c = 3 和no = 1 , 使得f(n) ≥ cg(n), for all n ≥ no. 先決定c的值，鎖定f(n)中的最大項之值(即: 3n)，c只要與該項的常數值相同即可!!再由c去推no。 3n+2 ≥ 3n  2 ≥ 0 (恒真，故no可任取!)。 f(n) = 5n2+3n-2, 則 f(n) = (n2). f(n) = (n2) if and only if 存在兩正數c = 5 和no = 2/3 , 使得f(n) ≥ cg(n), for all n ≥ no. 先決定c的值，鎖定f(n)中的最大項之值(即: 5n2)，c只要與該項的常數值相同即可!!再由c去推no。 5n2+3n-2 ≥ 5n2  3n-2 ≥ 0  取 no = 2/3。

30 Theta () 較 O 與  精確. Definition:
f(n) = (g(n)) if and only if 存在三正數c1, c2和no, 使得 c1 g(n) ≤ f(n) ≤ c2g(n), for all n ≥ no.

31  If f(n) = O(g(n))且f(n) = (g(n)), 則f(n) = (g(n)).
以定義來說明範例 f(n) = 3n+2, 則 f(n) = (n). f(n) = (n) if and only if 存在三正數c1 = 3 , c2 = 4 和no = 2 , 使得c1 g(n) ≤ f(n) ≤ c2g(n), for all n ≥ no. 用先前決定O 與 中c值的方式分別得到c1 與 c2 即可!!再由c1 與 c2去推no。 3n+2 ≤ 4n (用f(n) ≤ c2g(n)來找)  n ≥ 2 。  If f(n) = O(g(n))且f(n) = (g(n)), 則f(n) = (g(n)).

32 以f(n) = 3n+2 與 f(n) = 5n2+3n+2為例:
Big-O, Omega與Theta的關係 以f(n) = 3n+2 與 f(n) = 5n2+3n+2為例: 3n+2: 5n2+3n+2: Big-O Theta Omega n2 n3 n 2n n4 n 1 Big-O Theta Omega n3 n4 n2 2n n5 n2 n 1

33 Small-O (o) Definition: 與Big-O的比較:
f(n) = o(g(n)) if and only if 對任何正數c，會存在一個正數no, 使得f(n) < cg(n), for all n ≥ no. 與Big-O的比較: f(n) = O(g(n)) if and only if 存在兩正數c和no, 使得f(n) ≤ cg(n), for all n ≥ no. 例如: 2n = o(n2) 2n2 ≠ o(n2)，但是2n2 = O(n2)。

34 Small-Omega () Definition: 與Omega的比較:
f(n) = (g(n)) if and only if對任何正數c，會存在一個正數no, 使得f(n) > cg(n), for all n ≥ no. 與Omega的比較: f(n) = (g(n)) if and only if 存在兩正數c和no, 使得f(n) ≥ cg(n), for all n ≥ no. 例如: 5n2+3n+2 = (n) 5n2+3n+2 ≠ (n2)，但是5n2+3n+2 = (n2)

35 太奇怪而無法比較的函數 (如: 週期函數) Big-O Small-O Omega Theta Small-Omega

36 ▓ 使用極限(Limit)來決定Order
若我們想利用極限的方式証明f(n) = (g(n)) ( 僅表示某一個演算法分析方式的表示符號)，則:

37 邏必達法則 (L’ Hospital Rule)

38 Ex: Determine if f(n) = (g(n)) or neither
  O f(n) = log54n, g(n) = log45n Sol:

39 f(n) = n, g(n) = n3 Sol:

40 f(n) = n cot(n), g(n) = n tan(n)
Sol:

41 Note Log的底和Complexity無關 a. 若log f(n) = o(log g(n))，可保証f(n) = o(g(n))
b. 若log f(n) = (log g(n))，可保証f(n) = (g(n)) c. 若log f(n) = (log g(n))，不可保証f(n) = (g(n)) 兩函數的Complexity有可能無法比較 (Ex: 週期函數) Note 2說明 (反例) f(n) = 2lg n, g(n) = n (lg = log2) Sol: lg f(n) = lg n  lg 2 lg g(n) = 2 lg n  lg f(n) = (lg g(n))  f(n) = (g(n)) () ∵f(n) = 2lg n = n, g(n) = n2 ???

42 課後練習 課文內容: 習題: 洪捷演算法Ch. 1:
Example 1.7, Example 1.9, Example 1.10, Example 1.11 Example 1.12, Example 1.13, Example 1.15, Example 1.17, Example 1.18, Example 1.19, Example 1.24, Example 1.25, Example 1.26, Example 1.27, Example 1.28. 習題: 15, 16, 17, 18 (上學期資結Ch. 1有教), 24 21 請自行參考洪捷p.1-10定理3及例題7~10 洪捷演算法Ch. 1: 例 1~6 精選範例 1, 2

43 補 充

44 補 1: 常用的數學式子

45 log log n = log (log n) logkn = (log n)k a = blogba logcab = logca+ logcb Logca/b = logca- logcb logban = n logba logba = logca/ logcb logba = 1/ logab logb(1/a) = logba-1 = -logba a logbc= c logba

46 補 2: 輸入大小(the size of the input)的合理測量
在前面正課所提及之一般的演算法複雜度分析當中，我們通常將 “輸入到演算法中的資料量” 視為輸入大小 (Input Size)。 從n筆資料中，搜尋一筆user想要得到的資料 對n筆資料做由小到大的排序工作 將一個graph輸入到某演算法做處理 有時候對於稱呼某個參數為輸入大小要非常小心

47 某一演算法有n個輸入資料，其中最大值為L。若資料編碼方式為k進位編碼，則該演算法的Input Size大約為：
定義：(9.2節) 對於一個給定的演算法，輸入大小(Input Size)為該演算法用來表示所輸入之資料的字元數 (符號數) 範例： 某一演算法有n個整數型態的輸入資料，其中最大值為31，資料編碼方式為二進位編碼。 每一筆資料的字元數(符號數，位元數；即用來編碼的符號數目)為 log231+1 = 5 該演算法的Input Size為5n 某一演算法有n個輸入資料，其中最大值為L。若資料編碼方式為k進位編碼，則該演算法的Input Size大約為： n×logkL

48 補 3: 補充考題 Ex 1: Show the following equality is incorrect
(91交大) n2/log n = (n2) Sol 1: (以極限來做)

49 Sol 2: (以定義來做) 需同時符合n2/log n = O(n2)和n2/log n = (n2)。(夾擠法)
c>0與n0>0,  n2/log n  cn2, n  n0 1/log n  c, n  n0 但是，當n時， 1/log n 0。然而c是一個大於0的正數，我們找不到一個 c > 0。(矛盾)  n2/log n ≠ (n2) n2/log n = (n2)不成立!!!