人事请假系统.ppt

1、Advance Data StructureReview of Chapter 1,張啟中,Chapter 1 Basic Concepts,1.1 Overview: System Life Cycle 1.2 Algorithm Specification 1.3 Data Abstraction (Chapter 2) 1.4 Performance Analysis and Measurement,System Life Cycle,Example,請假處理子系統,審核驗證子系統,Algorithm Specification,演算法是由一序列的指令所組成。依序執行這些指令可以解決給定

2、的問題。演算法具有下列五大條件： 輸入(Input) 外界可提供零個或多個輸入資料。 輸出(Output) 必須最少有一個輸出的結果。 明確性(Definiteness) 每一個指令的功能都必須明確而不混淆。 有限性(Finiteness) 對任意的輸入資料，演算法必須在有限的時間內執行完成。 有效性（Effectiveness) 每一個指令必須非常基本：僅用紙筆即可完成。,Algorithm Describing,Natural language English, Chinese Instructions must be definite and effectiveness Graphic

3、representation Flowchart work well only if the algorithm is small and simple Pseudo language Readable Instructions must be definite and effectiveness Combining English and C In this text,Example,問題：設計一個演算法來測試一個正數 n 是否為質數。,作法：逐一檢查 2, 3, ., n-1 是否可以整除 n；若都無法 整除，則 n 是質數，否則不是質數。,範例：91 是否為質數？,2, 3, 4, 5,

4、 6, 7, 8, ., 76,範例：7 是否為質數？,2, 3, 4, 5, 6,1. 若 n 小於或等於1，則 n 不是質數； 2. 令 k = 2, 3, ., n-1，逐一檢驗： 3. 若 k 可以整除 n，則 n 不是質數； 4. 若以上所有的 k 值均無法整除 n，則 n 是質數；,輸入 一個自然數 n。 輸出 回答 n 是/否為質數。 明確性 每一行指令都很明確。 有限性 對任一個輸入的自然數 n，此演算法都 能在有限的時間內求出 n 是否為質數。 有效性 每一行指令都簡易至光用紙筆即可做出 的程度。,Example,Performance Analysis and Measur

5、ement,Criteria Is it correct? Is it readable? Performance Analysis (machine independent) Space complexity: storage requirement Time complexity: computing time Performance Measurement (machine dependent),Performance Analysis: Space complexity S(P)=C+SP(I),Fixed Space Requirements (C)Independent of th

6、e characteristics of the inputs and outputs instruction space space for simple variables, fixed-size structured variable, constants Variable Space Requirements (SP(I)depend on the instance characteristic I number, size, values of inputs and outputs associated with I recursive stack space, formal par

7、ameters, local variables, return address,Example,*Program 1.9: Simple arithmetic function (p.19)float abc(float a, float b, float c) return a + b + b * c + (a + b - c) / (a + b) + 4.00;*Program 1.10: Iterative function for summing a list of numbers (p.20)float sum(float list , int n) float tempsum =

8、 0; int i; for (i = 0; in; i+) tempsum += list i; return tempsum;,Sabc(I) = 0,Ssum(I) = 0,Example,*Program 1.11: Recursive function for summing a list of numbers (p.20) float rsum(float list , int n) if (n) return rsum(list, n-1) + listn-1;return 0; ,Ssum(I)=Ssum(n)= 4*(n+1),Recall: pass the address

9、 of the first element of the array int i; for (i = 0; i n; i+) count += 2; count += 3; return 0; ,float sum(float list, int n) float tempsum= 0; count+; /*for assignment */ int i; for(i= 0; i n; i+) count+; /* for the for loop */ tempsum+= listi; count+; /* for assignment */ count+; /* last executio

10、n of for */ count+;/* for return */ return tempsum; ,2n + 3 steps,Program Step Analysis: Tabular Method,float sum(float list, int n) float tempsum=0; int i; for(i= 0; i n; i+) tempsum+= listi; return tempsum; ,lines/e FrequencyTotal Steps = 1000 2000 3111 4000 51n+1n+1 6000 71nn 8000 9111 10000 = To

11、tal2n+3,Performance Analysis,一般而言，一個演算法完成執行所耗費的時間常是隨著輸入量（input size）的增加而增長，且兩者之間具有函數般的依存關係。以排序演算法為例：其輸入為陣列中的資料，資料的個數則為其輸入量。顯然地，當輸入量愈大時，排序所花的時間也會跟著增長。又以質數判斷演算法為例：其輸入為一個自然數 n，n 的大小則為此演算法的輸入量，因為判斷一個較大的自然數是否為質數通常會花較多的時間。 精確地分析一個演算法在各種輸入值下的效率，是一件異常繁複的工作。此外，如此做也只能得到估算的結果而已。,Asymptotic Notation(O, , ),Exac

12、t step count Compare the time complexity of two programs that computing the same function Difficult task of most of programs Asymptotic notation Big oh upper bound(current trend) Omega lower bound Theta upper and lower bound,分析演算法在所有可能的輸入組合下，最多 所需要的時間。,分析演算法在所有可能的輸入組合下，平均 所需要的時間。,分析演算法對何種輸入資料，所需花費的時

13、 間最少。,定義1-1：上限（asymptotic upper bound）(Big O),f (n) = O(g(n) 如果存在正數 c 和 n0 使得 對所有的 n, n n0, f (n) cg(n) 。,Big O 符號用於表達演算法最差狀況分析 所得的輸入量和時間兩者之間的成長倍率。,W 符號用於表達演算法最佳狀況分析 所得的輸入量和時間兩者之間的成長倍率。,定義1-3：(Theta, Q),f (n) = Q (g(n) 如果存在正數 c1, c2 和 n0 使得 對所有的 n, n n0, c1g(n) f (n) c2g(n) 。,重要定理,定理1-1：,定理1-2：,定理1-

14、3：f (n) = Q(g(n) 若且唯若 f (n) = O(g(n) 以及 f (n) = W(g(n) 。,Example,範例：驗證 3n + 2 = O(n)。,解：當 n 2 時，不等式 3n + 2 4n 成立，故得證。 （此處，定義 1-1 中的 n0 和 c 的值分別取為 2 和 4。）,下表列出一些常見的函數在不同 n 值下的函數值：,平方倍成長,立方倍成長,指數成長,對數成長,線性對數成長,n,由前述的的比較中，我們得知演算法的效率若以 big O 的的表之，由好至壞的順序如下表所示：,10 50 100 10,000 1,000,000,.01ms .05ms .10m

15、s 10.00ms 1.00ms,.03ms .28ms .66ms 130.03ms 19.92ms,.1ms 2.5ms 10ms 100ms 16.67min,1ms 125ms 1ms 16.67min 31.71yr,10 50 100 10,000 1,000,000,10ms 6.25ms 100ms 115.7d 3.17*1071yr,10sec 3.1yr 3171yr 3.17*10231yr 3.17*10431yr,1ms 13d 4*10131yr,run-time on a computer with power 109 instruction/sec,Examp

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

17、迴路即可。,範例：計算向量內積,需要 O(n) 時間。,int inner_product (int u, int v, int n) int i, sum = 0; for (i = 0; i n; i+) sum += ui*vi; return sum; ,範例：底下計算矩陣加法,的演算法需要 O(n2) 時間。,for (i = 0; i n; i+) for (j = 0; j n; j+) cij = aij + bij;,範例：底下計算矩陣乘法,的演算法需要 O(n3) 時間。,for (i = 0; i n; i+) for (j = 0; j n; j+) sum = 0;

18、for (k = 0; k n; k+) sum += aik * bkj; cIj = sum; ,測驗題：底下的程式需要多少時間？,Performance Analysis Conclusion,asymptotic 式的演算法分析技巧 ，雖可提供我們評判演算法的優劣，但是在實際運用上必須進一步分析。比方說：演算法 A 需要 103n 的步驟、演算法 B 需要 n2 的步驟。分析的結果演算法 A 是 O(n) 而演算法 B 是 O(n2)，但這並不是說演算法 A 一定比演算法 B 好 當 n 不大於103 的時候，演算法 B 就比演算法 A 有效率，因此在這個情形下，我們應該選擇演算法 B

19、 而不是演算法 A。 換句話說，在選擇演算法時，除了考慮其 order 外，也必須考慮所處理問題的大小（即 n ）。,Recursive Algorithm,Direct 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,Recurs

20、ive Programming Style,Function recursive() if (終止條件判斷式) /成立，終止遞迴 return; else (遞迴呼叫方式); ,Recursive Example 求 n!,iterative 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),

21、O(n),Performance Analysis,每次遞迴需 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 version 1 int factor(int n) 2 3 if (n=1) 4 return 1; 5 else 6 return n*factor(n-1); 7 ,Recursive Example: HANOI Towers,將 A 柱上所有的

22、碟子搬移到 B 柱 搬移的過程小碟始終要在大碟之上。 相傳印度恆河的僧侶只要將 A 柱上的 64 個碟子全部搬移到 B 柱，世界末日就來到。如果他們一秒鐘可搬移一個碟子，問世界末日何時來到？,A,B,C,Recursive Example: HANOI Towers,A,B,C,以上圖為例，要搬移 A 柱上的三個碟子到 B 柱，我們可以簡單的這樣想： 先將最上面二個小碟 (1-2) 搬到 C 柱。( recursive, n-1 ) 將留在 A 柱的大碟搬到 B 柱。 最後，再將 C 柱上的二個小碟 (1-2) 搬到 B 柱。 ( recursive n-1 ) ,1,Recursive Example: