演算法的效率分析.

Presentation on theme: "演算法的效率分析."— Presentation transcript:

1 演算法的效率分析

2 演算法的效率分析 什麼是有效率的演算法？電腦學家為此衡量準則提供了客觀的標準—分析演算法的執行時間和記憶體需求。以時間複雜度或空間複雜度來討論演算法的效率 解決相同的問題，演算法所用的時間複雜度和空間複雜度愈少愈好。 時間複雜度(time complexity)：一個程式或演算法所需的執行時間； 空間複雜度(space complexity)：一個程式或演算法所需的記憶體空間。

3 演算法的執行次數 程式1-4 陣列元素加總 int Sum(int data[],int n) { int summation=0; for (int i=0; i<n; i++) summation += data[i]; return summation; } 程式1-4將傳入整數陣列data 中的n個元素 (data[0]~data[n-1])，總加至整數變數summation中傳出。 程式1-5 陣列元素加總並計算所有指令執行的次數 int count = 0; // 全域變數宣告 count++; // 計算宣告 int 指令的執行 int Sum(int data[],int n) { int summation=0; for (int i=0; i<n; i++) { count++; // 計算 for 指令的執行次數 summation += data[i]; count++; // 計算 = 指令的執行次數; } count++; // 計算最後一次 for 指令的執行 count++; // 計算 return 指令的執行 return summation; 在程式1-4中加入一全域變數count，來加總所有指令執行的次數；新的程式將如程式1-5所示。

4 演算法的執行次數(續) 程式1-6 只保留程式1-5 的主體和加總count 的指令。
程式1-6 計算陣列元素加總所有指令執行的次數 count++; int Sum(int data[],int n) { count++; // 計算宣告 int 指令的執行 for (int i=0; i<n; i++) count += 2 count += 2; } 程式1-6 只保留程式1-5 的主體和加總count 的指令。 此程式的執行總次數為2n+4，其中 for 迴圈每執行一次，count會計數兩次；而迴圈共計有n次，所以for迴圈內即執行2n 次。

5 演算法複雜度的表示方法：O、Ω 和Θ 假設有兩個演算法都可解決問題P，其輸入資料量為n；演算法 A 的估算執行次數為 4n2+174，演算法 B 的估算執行次數為 n3+5n+6。(見下圖) 在 n>7 後 演算法 A 比 B 好

6 演算法複雜度的表示方法：O、Ω 和Θ 精確計算演算法的執行步驟或時間的工作過於繁瑣。 電腦處理的是大量的資料。
我們比較關心：資料量大的時候，演算法是否夠好。 精簡的方法分析： 演算法的複雜度：O ，「Big Ｏ」「大Ｏ」 問題的複雜度：Ω 最佳演算法： Θ

7 用大O表示時間複雜度 定義：f (n)=O (g (n)) 若且唯若存在兩個正整數c和n0，當nn0時，f (n)  cg (n)。
f(n)指的是演算法的執行時間（步驟），我們希望能找到g(n)；只要在nn0後，cg(n)一定會大於或等於f(n)，那麼就可以用O(g(n))來表示f(n)。

8 請注意在上圖中，當n  14 (=n0) 之後，cg(n) 一定會大於或等於f(n)（5n2  4n2+174），
所以O(n2)足以代表4n2+174 。

9 範例 4n+12 = O(n)，因為存在c=5，n0=12，使得n12後，4n+12 5n（或c=6，n0=6，使得n6後，4n+12  6n）； 10n+25 = O(n)，因為存在c=12，n0=13，使得n13後，10n+25  12n； 8n2+11n+18 = O(n2)，因為存在c=9，n0=13，使得n13後，8n2+11n+18  9n2； 6×2n+n2 = O(2n)，因為存在c=7，n0=4，使得n4後，6×2n+n2 7×2n；

10 範例 326 = O(1)，因為存在c=327，n0可任取，使得n n0後，326  327×1；
9n2+n+11  O(n)，因為找不到適當的c和n0，使得nn0後，9n2+11  cn； 100n3 = O(n4)，因為存在c=16，n0=8，使得n8後，100n3 16n4。

11 以大O表示法分辨演算法的優劣 O(1)稱為常數時間，即不論演法的步驟須需要多少指令，只要不像迴圈般重複執行，皆視為常數時間；
O(n)稱為線性時間，取其執行步驟的增加趨勢與n的增加趨勢為線性關係之意； O(n2)為平方時間；依此類推， O(2n)則稱為指數時間。 如此一來，我們會說O(logn)的演算法比O(n)來得有效率，O(n)比O(n2)來得有效率…。

12 O(2n) O(n2) n≤10 ，大O函數值的變化

13 O(n2) 10 ≤ n ≤ 100，大O函數值的變化

14 大O表示函數的優劣順序為： O(1)  O(logn)  O(n)  O(nlogn)  O(n2)  O(n3)  O(2n)

15 用Ω表示問題的難易程度 大O的符號是為了方便討論「演算法的複雜度」而設計引用的； Ω則不然，它是為了方便討論「問題的難易程度」而設計引用的。其定義如下，假設f, g0： 定義：f (n)=Ω (g (n)) 若且唯若 存在兩個正整數c和n0，當nn0時， f (n)cg (n)。

16 (a) 4n+12 =(n)，因為存在c=1，n0=1，使得n1後，4n+12  n；
(b) 10n+25 =(n)，因為存在c=10，n0=1，使得n1後，10n+25  10n； (c) 8n2+11n+18 =(n2)，因為存在c=1，n0=1，使得n1後，8n2+11n+18  n2； (d) 6×2n+n2 =(2n)，因為存在c=1，n0=1，使得n1後，6×2n+n2  1×2n；

17 範例 (e)326 =(1)，因為存在c=1，n0可任取，使得nn0後，326  1×1； (f)9n2+n+11 (n3)，因為找不到適當的c和n0，使得nn0後，9n2+11  cn3； (g)100n3 =(n2) =(n) =(1)，因為存在c=1，n0=，使得n1後，100n3  n2 n  1。

18 最佳 (optimal) 演算法 定義：f (n) = θ(g (n)) 若且唯若存在 參個正整數c1、c2和n0，當nn0時，
如果既可找到演算法 A 來解決問題 P，時間複雜度為O(g(n))，且又能証明解決問題 P 的最少代價亦為Ω(g(n))；則欲解決P的時間，至多要O(g(n))，至少為Ω(g(n))；不可能多於O(g(n))，也不可能少於Ω(g(n))（最多或最少都只是g(n)的常數倍），則演算法A是解決問題P的最佳 (optimal) 演算法。 定義：f (n) = θ(g (n)) 若且唯若存在 參個正整數c1、c2和n0，當nn0時， c1g (n)  f (n)  c2g (n)。

19 範例 4n+12 = θ(n)，因為存在c1=1、c2=5，n0=12，使得n12後，1n  4n+12  5n； 8n2+11n+18 = θ(n2)，因為存在c1=1、c2=9，n0=13，使得n13後，1n2  8n2+11n+18  9n2。

20 練 習

21 End