演算法分析 (Analyzing Algorithms)

Presentation on theme: "演算法分析 (Analyzing Algorithms)"— Presentation transcript:

1 演算法分析 (Analyzing Algorithms)
參考: 物件導向資料結構 — 使用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.

2 演算法分析 分析一個演算法指的是要對演算法所需要的資源(resources)進行預測。
資源(Resources):記憶體(memory),通訊(communication),頻寬(bandwidth),邏輯閘 (logic gate),時間(time)

3 演算法分析 演算法運行時間(running time)是指在特定輸入下所執行的基本操作或”步驟”的數目。
能方便地進行與機器無關的(machine-independent) 分析。

4 複雜度(Complexity) 一般我們使用 來評估演算法的執行時間與所佔用記憶體空間， 這些複雜度愈低，則表示演算法愈好。
時間複雜度(time complexity) 空間複雜度(space complexity) 來評估演算法的執行時間與所佔用記憶體空間， 這些複雜度愈低，則表示演算法愈好。 我們比較關注time complexity！

5 三種狀況 演算法的時間複雜度分析分為以下三種： 最佳狀況(best case)時間複雜度:考慮演算法執行時所需要的最少執行步驟數。
最差狀況(worst case)時間複雜度:考慮演算法執行時所需要的最多執行步驟數。 平均狀況(average case)時間複雜度:考慮所有可能狀況下演算法的平均執行步驟數。

6 最差狀況與平均狀況的分析 通常，我們只專注在找出最差狀況運行時間(worst-case running time) 理由:
是運行時間的上限(upper bound)。 最差狀況也經常發生。 平均狀況常常和最差狀況一樣差。例如:插入排序(insertion sort) 以及二次函數(quadratic function)。

7 一個用以測試質數的演算法 Algorithm Prime1(n): Input:一個大於2的正整數n Output:true或false(表示n是質數或不是質數) for i←2 to n-1 do if (n%i)=0 then return false return true 我們可以看出，輸入大於2的任意正整數n，若n是質數，則演算法Prime1需要執行整數除法求餘數(n%i)動作與整數比較((n%i)=0)動作n-2次之後，才可以知道n是質數。另外，若n不是質值，則演算法Prime1只要執行整數除法求餘數與整數比較動作1次，就可以知道n不是質數了。

8 另一個用以測試質數的演算法 我們可以看出，輸入大於2的任意正整數n，若n是質數，則演算法Prime2需要執行整數除法求餘數(n%i)動作與整數比較((n%i)=0)動作 -2次之後，才可以知道n是質數。另外，若n不是質值，則演算法Prime2只要執行整數除法求餘數與整數比較動作1次，就可以知道n不是質數了。

9 分析演算法Prime1 因此，我們很容易看出來，在最壞狀況(worst case)下，演算法Prime1的執行步驟次數與輸入的正整數n成正比關係；而在最佳狀況(best case)下，演算法Prime1的執行步驟次數為與輸入的正整數n無關的某個常數。也就是說，演算法Prime1具有線性的(linear) 最差狀況時間複雜度(正比關係即為線性關係)與常數的(constant) 最佳狀況時間複雜度。

10 分析演算法Prime2 我們也很容易看出來，在最壞狀況(worst case)下，演算法Prime2的執行步驟次數相依於輸入的正整數n的平方根值；而在最佳狀況(best case)下，演算法Prime2的執行步驟次數為與輸入的正整數n無關的某個常數。也就是說，演算法Prime2具有平方根的(square root) 最差狀況時間複雜度與常數的(constant) 最佳狀況時間複雜度。

11 漸進記號(Asymptotic Notation)
一般而言，我們使用所謂的漸進記號(asymptotic notation)來分析演算法的複雜度，漸進記號考慮的是演算法在處理資料範圍漸進於無窮大，或說是問題大小(problem size)漸進於無窮大時的狀況。 在演算法的資料處理範圍(或處理資料量)較小時，不管是有效率的(執行步驟數較少)或是沒有效率的(執行步驟數較多)演算法通常都可以很快的執行完畢，在這個狀況下，演算法的時間複雜度好壞的差距比較不明顯。 當演算法處理資料範圍(或處理資料量)相當大時，有效率的演算法通常還是可以很快的結束；而一些極度沒有效率的演算法則很可能需要幾日、幾月甚至於幾年才能執行完畢。因此，我們僅關心演算法在處理資料範圍(或處理資料量)非常大的狀況，這是為什麼分析演算法時間複雜度要採取漸進記號的原因。

12 量級(Order) 在演算法處理資料範圍漸進於無窮大的狀況下，演算法的時間複雜度會漸進於一個量級(order)。一般而言，演算法的時間複雜度是一個多項式，當演算法處理資料範圍漸進於無窮大時，時間複雜度的多項式中除了最高次方的項目外，其他的部分都可以被忽略；而同時，最高次方項目的係數也同時可以被忽略。 例如，若一個演算法的時間複雜度為n-2，則當n相當大(漸進於無窮大)時，此演算法的時間複雜度漸進於n，屬於一次方或稱線性(或正比)量級(稱為線性的原因是因為一次方多項式於平面座標上可描繪出直線圖形)；若一個演算法的時間複雜度為35n2+12n+11，則當n相當大(漸進於無窮大)時，此演算法的時間複雜度漸進於n2，屬於平方量級；而若一個演算法的時間複雜度為28n3+1245n2+162n+321，則當n相當大時(漸進於無窮大時)，此演算法的時間複雜度漸進於n3(屬於立方量級)。

13 大O記號(Big-O Notation) 我們通常使用大O記號(Big-O notation)的來表示這種漸進情形，大O記號可以說是一個用來表示演算法時間複雜度量級(order)的記號，我們將時間複雜度與大O記號的關係整理如下： 一般而言，若是一個演算法的時間複雜度表示為一個多項式，則我們取這個多項式的最高次方為其時間複雜度的量級(order)，並且將此量級以大O記號表示(O 代表order之意)。

14 定義大O記號 以下我們正式定義大O記號： [定義] 大O記號 (Big-O notation) 令f(n)與g(n)是由非負整數對應至非負實數的函數，若存在正實數常數c>0和正整數常數n0使得對所有的nn0而言，f(n)cg(n)成立，則我們說f(n)=O(g(n))。(唸作 「f(n)是屬於Big-O of g(n)」，比較正式的英文唸法為「f of n is of Big-O of g of n」)。 例如，針對35n2+12n+11而言，存在c=58和n0=1(58由 求得)，使得當nn0=1時，35n2+12n+11cn2=(58n2)成立，因此，我們說35n2+12n+11=O(n2)。

15 漸近式上限 (Asymptotic Upper Bound)
Def: f(n) = O(g(n)) “上限(upper bound)" iff  c, n0  |f(n)|  c|g(n)|  n  n0 e.g. f(n) = 3n2 + 2 g(n) = n2  n0=2, c=4  f(n) = O(n2) e.g. f(n) = n3 + n = O(n3) e. g. f(n) = 3n2 + 2 = O(n3) or O(n100 )

16 漸近式上限 (Asymptotic Upper Bound)

17 漸近式下限 (Asymptotic Lower Bound )
Def : f(n) = (g(n)) “下限(lower bound)” iff  c, and n0,  |f(n)|  c|g(n)|  n  n0 e. g. f(n) = 3n2 + 2 = (n2) or  (n)

18 漸近式下限 (Asymptotic Lower Bound )

19 Theta記號 Def : f(n) = (g(n))
iff  c1, c2, and n0,  c1|g(n)|  |f(n)|  c2|g(n)|  n  n0 e. g. f(n) = 3n2 + 2 =  (n2)

20 Theta記號 f(n) = (g(n))

21 Theorem 對任意兩函數f(n) 與 g(n), ⇔ &

22 盡可能將量級降低 我們發現某些量級在演算法的處理資料範圍或處理資料量(即問題大小，problem size)還不是很大的情況之下，演算法的時間複雜度的執行步驟對照數值(即執行時間，execution time)就已經是相當大的值了，這表示演算法需要運算相多的執行步驟，當然也就是要執行相當久的時間。因此，如何設計一個時間複雜度量級較低的演算法是我們必須一直擺在心中的最重要目標。

23 量級的比較 以下是演算法時間複雜度量級的高低次序比較，比較低的量級表示執行步驟較少，也就是代表演算法的執行時間較短。
O(1) < O(log n) < O( ) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n) O(n!)  O(nn)

24 演算法時間複雜度的大O記號表示及其量級 時間複雜度 以大O記號表示 量級 162 O(1) 一次方常數(constant)量級
63log n+4 O(log n) 次線性(對數)(sub-linear, logarithmic)量級 O( ) 平方根(square root)量級 n-2 O(n) 線性(linear)量級 156n+81 35n2+12n+11 O(n2) 平方(quadratic)量級 28n3+1245n2+162n+321 O(n3) 立方(cubic)量級 142n+457n3+248n2-45n+81 O(2n) 指數(exponential)量級

25 演算法各種時間複雜度的執行步驟對照數值 log n n n logn n2 n3 2n 1.00 1 2 1.41 4 8 2.00 16
1.00 1 2 1.41 4 8 2.00 16 64 3 2.83 24 512 256 4.00 4,096 65,536 5 5.66 32 160 1,024 32,768 4,294,967,296

26 演算法各種時間複雜度量級成長圖

27 演算法各種時間複雜度量級成長圖(對數圖)

28 多項式時間演算法 vs. 指數時間演算法 對於任意時間複雜度為O(p(n))的演算法，其中若p(n) 為一個多項式函數，則此演算法為多項試時間演算法(polynomial time algorithm)。另一方面，若p(n)不是多項式函數，則此演算法稱為指數時間演算法(exponential time algorithm)

29

30

31 上高斯符號 (ceiling) 與下高斯符號 (floor)

32 模數運算(modular operation)
對任意整數a 與 任意正整數n, 數值a mod n 為 a/n　的餘數 : a mod n =a -a/nn. 若(a mod n) = (b mod n)， 我們可以寫成 a  b (mod n)並且說a 與b 在mod n (modulo n)下為等價(equivalent)的。 若我們寫a ≢ b (mod n) 則a 與b 在mod n之下並不為等價的。