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

▓ 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

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

Def: The step-by-step procedure that is used to solve the problem is called algorithm. 完成特定功能之有限個指令之集合。同時，需滿足下列5個性質： Input: 外界至少提供0個輸入 Output: Algorithm至少產生1個輸出結果 Definiteness (明確): 每個指令必須是Clear and Unambiguous Finiteness (有限性): Algorithm在執行有限個步驟後，必定終止 Effectiveness (有效性): 用紙跟筆即可追蹤Algorithm中執行的過程及結果

其中，Program不一定會滿足特性4，但是Algorithm一定會滿足!! Ex: 軍事防衞系統、提款機系統、作業系統 這就是Program與Algorithm不同之處

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

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

問題演算法:

問題2: 字串完全匹配問題 (The Exact String Matching Problem) Input 字串 P –– the pattern 字串 T –– the text Output 將位於字串T中，與字串 P 完全匹配的位置找出來。

範例: Text string T = AGCTTGATT Pattern string P = GATT Output: 6 (比到第6次) 1 2 3 4 5 6 7 8 9 A G C T G A T

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

▓ The Importance of Developing Efficient Algorithms Regardless of how fast computers become or how cheap memory gets, efficiency will always remain an important consideration. 排序問題 (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)

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

▓ Analysis of Algorithms To determine how efficiently an algorithm solves a problem, we need to analyze the algorithm. 一個Algorithm的好壞，通常有兩個評估因子： Space (空間): Space Complexity Time (時間): Time Complexity

空間複雜度(S(P))通常來自於兩方面： Space Complexity 空間複雜度(S(P))通常來自於兩方面： Fixed Space Requirement: C Instruction Space (即：程式碼大小) 變數 (Simple variables, 如：int, float, …) Constant Fixed size structure variables (如：陣列、紀錄…等，用struct或class來宣告) Variable Space Requirement: SP(I) 參數: 若structure variables是以call by value為主的之參數傳遞方式 (如：陣列…) 由於Recursive Call所需要的Stack空間 S(P) = C + SP(I) [C是固定常數，SP(I)是會變動的變數] 非主要考量 (∵C這個值在程式設計完成後就固定了) 主要考量 (∵S(P)會與SP(I)呈線性關係)

SP(I) = 0 (∵沒有structure variable, 也沒有Recursive Call) 例 1. Simple variables SP(I) = 0 (∵沒有structure variable, 也沒有Recursive Call)

例 2. SP(I): 有無Stack空間花費 沒有 (∵沒有Recursive Call) 有structure variable，考量參數傳遞是不是call by value: = 4n, list[ ]若為call by value 傳遞 (根據主程式所傳來的數值型態與數值多寡) = 0 (或一常數，即起始位址值), list[ ]若為call by address 傳遞 (∵主程式只傳陣列的起始位址，沒有變動空間需求)

例 3. 假設: int佔4 bytes, float佔4 bytes, Address佔2 bytes, list[ ]以call by address傳遞 SP(I): 有structure variable，但參數傳遞方式不是call by value 沒有變動空間需求 有無Stack空間花費 有 (∵有Recursive Call) 發生一次遞迴所須的Stack空間為: SP(I)=(參數”list”之起始位址+參數“n”)+返回位址 = (2+4)+2 = 8 bytes 共有n次Recursive call   SP(I) = 8n bytes.

Time Complexity In general, the running time of an algorithm increases with the size of the input, and the total running time is roughly proportional to how many times some basic operation (such as a comparison instruction) is done. We therefore analyze the algorithm‘s efficiency by determining the number of times some basic operation is done as a function (或稱Time function, Complexity function亦可) of the size of the input. T(n) is defined as the number of times the algorithm does the basic operation for an instance of size n.

例 1.  T(n) = 1+2n+1+1 = 2n+3. 每行指令的執行次數 程式 1 n+1 n 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. 不可執行!!∵就系統執行的角度而言，變數宣告只是在Compile時，在M.M.中建立一個空間，但不會產生相對應的執行碼!!除非在宣告的同時有指派一個初始值，指派的動作就會有相對應的執行碼產生以供程式執行時使用。

例 2.  T(n) = (n+1)+n+1 = 2n+2. 每行指令的執行次數 程式 n+1 n 1 float rsum(float list[ ], int n) { if (n>0) return rsum(list, n-1)+ list[n-1]; } return list[0];  T(n) = (n+1)+n+1 = 2n+2. 遞迴運算!!∵本題是針對list[ ]做累加的計算，即：list[n]+ list[n-1]+…+list[0]。

Logarithmic Loops Multiply Loops i = 1 loop (i < n) basic operation i = i  2 end loop ∵i  1, 2, 4, 8, 16,…, 2k  2k < n  k < log2n  T(n) = log2n Divide Loops i = n loop (i >= 1) basic operation i = i / 2 end loop ∵i  n/2, n/4, n/8,…, n/2k n/2k >=1  n >= 2k  log2n >= k  T(n) = log2n

Nested loops Dependent Quadratic T(n) = 1+2+3+4+…+n i = 1 =n(n+1)/2 loop (i <= n) j = 1 loop (j <= i) basic operation j = j + 1 end loop i = i + 1 T(n) = 1+2+3+4+…+n =n(n+1)/2  T(n1) = n  T(n2) = T(n)/T(n1) = (n+1)/2  

有許多被設計出來的演算法，當輸入資料的情況不同時，所分析出來的執行次數也有所不同。 因此，在分析這些演算法的執行次數時，可依據輸入資料的不同情況區分成三個Case來加以分析: The worst case (最差情況) the maximum number of times the algorithm will ever do its basic operation for an input size of n. W(n): worstcase time complexity The best case (最佳情況) the minimum number of times the algorithm will ever do its basic operation for an input size of n. B(n): best-case time complexity The average case (平均情況) the average (expected value) of the number of times the algorithm does the basic operation for an input size of n. A(n): average-case time complexity

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

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

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

T(n) is called the every-case time complexity of the algorithm, because The basic operation is always done the same number of times for every instance of size n. The determination of T(n) is called an every-case time complexity analysis.

A best-case analysis would be of little value. For algorithms that do not have every-case time complexities, we do worst-case and average-case analyses much more often than best-case analyses. An average-case analysis is valuable because it tells us how much time the algorithm would take when used many times on many different inputs. Ex: A sorting algorithm that was used repeatedly to sort all possible inputs. A worst-case analysis is valuable because it would give us an upper bound on the time taken by the algorithm. Ex: A system that monitored a nuclear power plant A best-case analysis would be of little value. It is usually harder to analyze the average case than it is to analyze the worst case. (Worst Case最常被討論)

▓ Asymptotic Notation (漸近式表示) 前面所提到的執行次數，可利用漸近式符號予以表示。 主要原因： 有些程式間實際執行次數看似不同，但是在電腦上執行的效能卻差不多。 指令有的簡單，有的複雜。如: 浮點數運算比整數運算難 除法和加法運算的複雜性不同 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

一般演算法分析常見的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

Figure 1.3: • Growth rates of some common complexity functions

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

An Intuitive Introduction to Order Functions such as: 5n2 5n2 + 100 0.1n2 + n + 100 eventually the quadratic term dominates this function. When an algorithm's time complexity is in (n2), the algorithm is called a quadratic-time algorithm, a (n2) algorithm, or the algorithm is (n2). Ordinarily an algorithm has to be (n lg n) or better for us to assume that it can process extremely large instances in tolerable amounts of time.  僅表示某一個演算法分析方式的表示符號 (n2)

An Rigorous Introduction to Order 共有五種漸近式表示方法： Big-O (O) Omega () Theta () Small-O (o) Small-Omega ()

執行次數T(n)可透過下列步驟轉換成Big-O 表示法: Big-O (O) Upper bound of f(n). 在一個多項式中，取最大項當成是理論上限，即程式執行時花費時間的成長率。 執行次數T(n)可透過下列步驟轉換成Big-O 表示法: 先將多項式中的所有常數改寫成 1. 保留最高變數項，其它的變數項將之刪除. 例： f(n) = 3n+2, 則 f(n) = O(n). f(n) = 5n2+3n+2, 則 f(n) = O(n2).

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)：執行時間的成長率。

Definition說明: 只要n大到某一個程度 (大過n0，通常假設無窮大)，就保証 f(n) 函數的數值一定小於等於 g(n) 函數以及其常數倍。 亦即在最壞 (worst case) 的情況下，f(n)函數的成長最多到達g(n)，而不會超過它!!

以定義來說明範例 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。

同理, f(n) = 5n2+3n+2 的Big-O 為 O(n2), 也可以為O(n3), 乃至O(2n). 前面所提例子中的f(n) = 3n+2, 其Big-O為 O(n), 然而, O(n2), O(n3), 乃至O(2n)也都是3n+2的上限值; 同理, f(n) = 5n2+3n+2 的Big-O 為 O(n2), 也可以為O(n3), 乃至O(2n). 原因: f(n) = O(g(n))這個式子只說明了當n  n0時, 若f(n) ≤ cg(n), 則g(n)的常數倍數是f(n)的上限值，但並不能看出該上限值是多高!! 但是, 在實際應用上為了要使f(n) = O(g(n))這個式子更有意義, g(n)必須要儘量小。 所以, 3n+2的Big-O應為 O(n), 不說 3n+2 = O(n3)…, 即使這些式子也是對的。

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.

Definition說明: 只要n大到某一個程度 (大過n0，通常假設無窮大)，就保証 f(n) 函數的數值一定大於等於 g(n) 函數以及其常數倍。 亦即在最好 (best case) 的情況下，f(n)函數的成長只能到達g(n)!!

以定義來說明範例 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。

前面所提例子中的f(n) = 3n+2, 其Omega為 (n), 然而, (1)也是3n+2的下限值; 同理, f(n) = 5n2+3n+2 的Omega 為 (n2), 也可以為(n), 乃至(1). 原因: f(n) = (g(n))這個式子只說明了當n  n0時, 若f(n)  cg(n), 則g(n)的常數倍數是f(n)的下限值，但並不能看出該下限值是多低!! 但是, 在實際應用上為了要使f(n) = (g(n))這個式子更有意義, g(n)必須要儘量大。 所以, 3n+2的Omega應為 (n), 不說 3n+2 = (1)…, 即使這個式子也是對的。

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.

Definition說明: 在夠大的n值時(大過n0，通常假設無窮大) ，如果存在有正的常數c1與c2，來讓f(n)夾於c1 g(n)與c2 g(n)之間，則f(n)即屬於(g(n)) 之集合。

 If f(n) = O(g(n))且f(n) = (g(n)), 則f(n) = (g(n)). 以定義來說明範例 f(n) = 3n+2, 則 f(n) = (n). f(n) = O(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)).

以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

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

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)

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

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

邏必達法則 (L’ Hospital Rule)

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

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

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

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) = n2 (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 ???

課後練習 課文內容: Exercises: 洪捷演算法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. Exercises: 15, 16, 17, 18 (上學期資結Ch. 1有教), 24 21 請自行參考洪捷p.1-10定理3及例題7~10 洪捷演算法Ch. 1: 例 1~6 精選範例 1, 2

補 充

補 1: Time Complexity 相關議題 計算某一指令 (ex: x=x+1) 的執行次數或Big-O

給程式片段，統計loop內執行次數與Big-O 例 1: 求x=x+1之執行次數與Big-O. Sol: 執行次數: For i = 1 to n do For j = 1 to i do x = x+1 end i值 i = 1 i = 2 … i = n j值 j = 1 to 1 j = 1 to 2 j = 1 to n x=x+1 執行1次 執行2次 執行n次  O(n2)

例 2: 求x=x+1之執行次數與Big-O. Sol: 執行次數: log2n  n/21  n/22  O(log2n) i = n = n/2 = n/4 = … = n/2k = 1  2k = n 執行次數: log2n i = n; (n>0) while (i >0) do x = x+1; i = i/2; end  n/21  n/22  O(log2n)

例 3: 求x=x+1之執行次數與Big-O. For i = 1 to n do For j = 1 to i do For k = 1 to j do x = x+1; end; end

Sol: 執行次數:  O(n3) 共1次 共3次 共6次 共(1+2+…+n)次 n(n+1)/2 i值 i = 1 i = 2 i = n j值 j = 1 to 1 j = 1 to 2 j = 1 to 3 j = 1 to n k值 k = 1 to 1 k = 1 to 2 k = 1 to 3 k = 1 to n x=x+1 執行1次 執行2次 執行3次 執行n次 共1次 共3次 共6次 共(1+2+…+n)次 n(n+1)/2  O(n3)

例 4: 求x=x+1之執行次數與Big-O. For k = 1 to n do For i = 1 to k do (Hint: k2 – (i = j的次數)) For k = 1 to n do For i = 1 to k do For j = 1 to k do if (i ≠ j) then x=x+1; end; end

Sol: 執行次數: i = j 的 情況  O(n3)

補 2: 常用的數學式子

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

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

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)不成立!!!

補 4: Reasonable measure of the size of the input Sometimes we must be cautious about calling a parameter the input size. A reasonable measure of the size of the input is the number of symbols used to encode . If we use binary representation, the input size will be the number of bits it takes to encode n, which is lg n + 1 (或 lg n). For example, Therefore, the size of the input n = 13 is 4.