如何设计一个时间复杂度量级较低的演算法是我们必须一直摆在心中.ppt

Floor and ceiling Modular arithmetic For any integer a and any positive integer n, the value a mod n is the remainder (or residue) of the quotient a/n : a mod n =a -?a/n?n. If(a mod n) = (b mod n). We write a ? b (mod n) and say that a is equivalent to b, modulo n. We write a ? b (mod n) if a is not equivalent to b modulo n. Analyzing Algorithms Based on: 物件導向資料結構 — 使用Java語言, 江振瑞 著, 松崗圖書公司, 2005. Introduction to the Design and Analysis of Algorithms -- A strategic approach, 2E, R.C.T. Lee et. al., NcGraw Hill, 2005. Introduction to Algorithms, Cormen et. al., MIT Press. Analyzing algorithms Analyzing an algorithm has come to mean predicting the resources that the algorithm requires. Resources: memory, communication, bandwidth, logic gate, time. We usually assume that the algorithm is performed on a processor with RAM Analyzing algorithms The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed. It is convenient to define the notion of step so that it is as machine-independent as possible Complexity 一般我們使用 時間複雜度(time complexity) 空間複雜度(space complexity) 來評估演算法的執行時間與所佔用記憶體空間， 這些複雜度愈低，則表示演算法愈好。 我們比較關注time complexity！ Three Cases 演算法的時間複雜度分析分為以下三種： 最佳狀況(best case)時間複雜度:考慮演算法執行時所需要的最少執行步驟數。 最差狀況(worst case)時間複雜度:考慮演算法執行時所需要的最多執行步驟數。 平均狀況(average case)時間複雜度:考慮所有可能狀況下演算法的平均執行步驟數。 Usually, we concentrate on finding only on the worst-case running time Reason: ?It is an upper bound on the running time ?The worst case occurs fair often The average case is often as bad as the worst case. For example, the insertion sort. Again, quadratic function. Worst-case and average-case analysis An Alg. for Testing Primes 我們可以看出，輸入大於2的任意正整數n，若n是質數，則演算法Prime1需要執行整數除法求餘數(n%i)動作與整數比較((n%i)=0)動作n-2次之後，才可以知道n是質數。另外，若n不是質值，則演算法Prime1只要執行整數除法求餘數與整數比較動作1次，就可以知道n不是質數了。 Algorithm Prime1(n):Input:一個大於2的正整數nOutput:true或false(表示n是質數或不是質數)for i←2 to n-1 do if (n%i)=0 then return falsereturn true 我們可以看出，輸入大於2的任意正整數n，若n是質數，則演算