講師:郭育倫 d95037@csie.ntu.edu.tw 第2章 效能分析 講師:郭育倫 d95037@csie.ntu.edu.tw

本章學習重點 基本概念 時間複雜度 空間複雜度 遞迴公式

解決問題的步驟(1/2) 演算法的設計策略 哪些方法是可行的？ 那個方法比較適合？ 暴力法（brute force） 分割處理法（divide and conquer, 各個擊破法） 貪婪演算法（greedy method, greedy approach） 動態程序規劃（dynamic programming） 回溯法（backtracking） 分支設限法（branch and bound） 資料結構 哪些方法是可行的？ 那個方法比較適合？

解決問題的步驟(2/2) 效能評估 效能量測 效能分析 直接利用實驗的方式，計算所花費的資源。 結果會比較精確，但是需要花較多的時間 。 演算法導論，探矽工作室 解決問題的步驟(2/2) 效能評估 效能量測 直接利用實驗的方式，計算所花費的資源。 結果會比較精確，但是需要花較多的時間 。 效能分析 找出該演算法所進行的各種運算，分析其所花費的資源。 方便做快速的判斷。

演算法導論，探矽工作室 基本概念 隨機存取機器的計算模型 最差與平均情況的分析 效率的差異

計算模型 Why? What? How? 方便我們發展演算法的運算模式和其使用資源的分析 單一處理器 演算法導論，探矽工作室 計算模型 Why? 方便我們發展演算法的運算模式和其使用資源的分析 What? 單一處理器 隨機存取機器(Random Access Machine, RAM) How? 其指令會一個接著一個順序執行，而不會同時執行。 包含真實電腦中常出現的指令： 運算（加減乘除、餘數、最大值、最小值等） 資料移動（載入、儲存） 控制（條件與非條件分支、副程式的呼叫與返回） 這些指令都會花費一定的時間。

程式運算 v.s. 數學式 內部迴圈 分析需要估計內部迴圈的重複次數，我們可以將程式轉換成數學運算來看 高次方的項位會「主宰」運算的次數 演算法導論，探矽工作室 程式運算 v.s. 數學式 內部迴圈 通常只有少數指令會在迴圈中不斷地被呼叫。 分析需要估計內部迴圈的重複次數，我們可以將程式轉換成數學運算來看 高次方的項位會「主宰」運算的次數 例如3n2+11n-45 常數項雖然也會影響運算次數， 但是當n值越大時，運算變化會很明顯地變得更大，而此時就會讓後面的常數項在概略估計時變得微不足道。 執行時間的成長度（order of growth）\ 成長速率（rate of growth）

演算法導論，探矽工作室 最差與平均情況的分析 我們注重的情況 最差情況 平均情況 一般來說，輸入的資料應該介於最佳和最糟兩者之間，即平均情況

注重最差情況的理由 一個演算法的最差情況執行時間是任何輸入的執行時間上限 有一些演算法的最差情況常常發生 平均情況與最差情況一樣糟糕 演算法導論，探矽工作室 注重最差情況的理由 一個演算法的最差情況執行時間是任何輸入的執行時間上限 知道上限可以讓我們保證此演算法不會花費更長的時間，並且不希望會有更糟的情況發生 有一些演算法的最差情況常常發生 例如在搜尋資料庫特定資料的時候，最差的情況發生在該資料不存在於資料庫中。然而尋找不存在資訊的情況卻常常發生 平均情況與最差情況一樣糟糕 某些時候我們會發現計算平均情況所得的時間與最差情況是相同的。

效率的差異 解決相同問題的不同演算法，通常在效率上會有差異，而且比硬體與軟體的差異還來得大。 範例：排序演算法 演算法導論，探矽工作室 效率的差異 解決相同問題的不同演算法，通常在效率上會有差異，而且比硬體與軟體的差異還來得大。 範例：排序演算法 「插入排序」需時c1n2 ，用快的A電腦執行 「合併排序」需時c2nlog2n，用慢的B電腦執行 A電腦每秒執行10億個指令，B電腦每秒執行1000萬個指令，則可知A電腦比B電腦快1000倍 假設要排序一個100萬個數字的陣列，c1=2，c2=50 在A電腦花費 2 × (106)2 / 109 = 2000 秒 在B電腦花費 50 × (106)log2(106) / 107 = 100 秒

時間複雜度 我們往往以一種「概量」的精神作為衡量程式執行時間的準則，稱為「時間複雜度」（time complexity） 演算法導論，探矽工作室 時間複雜度 我們往往以一種「概量」的精神作為衡量程式執行時間的準則，稱為「時間複雜度」（time complexity） 定義T(n)，表示在一個完全理想狀態的計算機中其程式所執行的實際指令次數。對於輸入量n而言，它的最大執行時間就是時間複雜度 時間複雜度實際上只表示實際次數的一個量度層級，並不是真正的執行次數 漸進表示法（asymptotic notation） Θ符號表示 Ο符號表示 Ω符號表示

演算法之時間複雜度 (Time Complexity) 時間複雜度影響因素: 程式處理之輸入量 Algorithm之寫法 Compiler之功效 (理論上無法得知) 執行機器之速度 (理論上無法得知)

演算法 計次範例一

演算法 計次範例二

演算法 計次範例三 (費式序列)(非遞迴)

Θ符號表示(1/2) 由上限與下限來逼近一個函數 定義 範例 演算法導論，探矽工作室 Θ符號表示(1/2) 由上限與下限來逼近一個函數 定義 f(n) = Θ(g(n))，若且唯若存在大於0的常數c1、c2、n3，使得對所有n值而言，n ≥ n0時，c1g(n) ≤ f(n) ≤ c2g(n)均成立 g(n)可同時代表f(n)的上限與下限 範例 3n+2=Θ(n)

Θ符號表示(2/2) 直觀上在決定漸進界線時，函數的較低階項目可以被忽略 演算法導論，探矽工作室 Θ符號表示(2/2) 直觀上在決定漸進界線時，函數的較低階項目可以被忽略 對任何多項式 ，其中ai是常數，並且ad>0，我們會得到p(n)= Θ(nd) Θ(1) 任何常數都是0次多項式，例如p(n)=5，我們可以把任何常數函式表示為Θ(n0)，或是Θ(1) 表示一個與某個變數相關的常數或是常數函數

Ο符號表示 表示函數的漸進上限 定義 也用來描述演算法的最差情況其執行時間的界線 範例 演算法導論，探矽工作室 Ο符號表示 表示函數的漸進上限 定義 對於f(n)=O(g(n))而言，存在正常數c與n0，對所有的n ≥ n0的值，0 ≤ f(n) ≤ cg(n)成立 g(n)的常數倍數，是f(n)的漸進上限，不過沒有明確表示出此上限是如何接近 也用來描述演算法的最差情況其執行時間的界線 範例 下圖的雙層巢狀迴圈裡，可以得到最差情況執行的時間為O(n2)

演算法導論，探矽工作室 雙層巢狀迴圈示意圖

常見的Ο函數與函數的實際值 函數 名稱 函數的實際值 Ο(1) 常數 - Ο(logn) 對數 1 2 3 4 5 Ο(n) 線性 8 16 演算法導論，探矽工作室 常見的Ο函數與函數的實際值 函數 名稱 函數的實際值 Ο(1) 常數 - Ο(logn) 對數 1 2 3 4 5 Ο(n) 線性 8 16 32 Ο(nlogn) nlogn 24 64 160 Ο(n2) 平方 256 1,024 Ο(n3) 3次方 512 4,096 32,768 Ο(2n) 指數 65,536 4,294,967,296 Ο(n!) 階乘

演算法導論，探矽工作室 常見的Ο函數成長關係圖

演算法導論，探矽工作室 定理2.1 如果 是一個d次多項式，則 證明 令C是f(n)中所有係數ai的絕對值當中最大的那個。則

定理2.1的延伸法則 範例 假設f(n)=n3+n，g(n)=n2+3n+1 則：f(n)=Ο(n3) g(n)=Ο(n2) 演算法導論，探矽工作室 定理2.1的延伸法則 範例 假設f(n)=n3+n，g(n)=n2+3n+1 則：f(n)=Ο(n3) g(n)=Ο(n2) Ο(f(n)+g(n))=Ο(n3) Ο(f(n)g(n))=Ο(n5)

Ω符號表示 估算函數f的下限值 定義 也用來表示最佳情況的執行時間界線 演算法導論，探矽工作室 Ω符號表示 估算函數f的下限值 定義 f(n) = Ω(g(n))，若且唯若存在大於0的常數c和n0，使得對所有n值而言，n ≥ n0時，f(n) ≥ cg(n)均成立 g(n)就可以看成是f(n)的下限 也用來表示最佳情況的執行時間界線

漸進函數的屬性 遞移性（transitivity） 反身性（reflexivity） 對稱性（symmetry） 演算法導論，探矽工作室 漸進函數的屬性 遞移性（transitivity） f(n)= Θ(n)，且g(n)= Θ(h(n))，則f(n)= Θ(h(n)) f(n)= O(n)，且g(n)= O(h(n))，則f(n)= O(h(n)) f(n)= Ω(n)，且g(n)= Ω(h(n))，則f(n)= Ω(h(n)) 反身性（reflexivity） f(n)= Θ(f(n)) f(n)=O(f(n)) f(n)= Ω(f(n)) 對稱性（symmetry） 若且為若g(n)= Θ(f(n))，才存在f(n)= Θ(g(n)) 移位對稱（transpose symmetry） 若且為若g(n)= Ω(f(n))，才存在f(n)=O(g(n))

空間複雜度 執行完一個程式所需要的記憶體空間 也是用「概量」的精神來衡量，同樣使用Ο、Θ、Ω等符號來做為它的漸進表示 主要包含三個部份 演算法導論，探矽工作室 空間複雜度 執行完一個程式所需要的記憶體空間 如果所需的記憶體太大，可能會大大增加執行的時間，甚至不能執行 也是用「概量」的精神來衡量，同樣使用Ο、Θ、Ω等符號來做為它的漸進表示 主要包含三個部份 指令空間（instruction space） 資料空間（data space） 環境堆疊空間（environment stack space）

遞迴堆疊空間 使用遞迴函式（recursive function）時，編譯器一般的做法 遞迴函式所需的堆疊空間也稱為遞迴堆疊空間 演算法導論，探矽工作室 遞迴堆疊空間 使用遞迴函式（recursive function）時，編譯器一般的做法 每呼叫一次遞迴函式時，就將函式的返回位址（return address）、參數（function parameters）和區域變數（local variables）儲存一份在環境堆疊中 遞迴有幾層，其需儲存在環境堆疊中的返回位址、函式參數和區域變數就有多少份 遞迴函式所需的堆疊空間也稱為遞迴堆疊空間

計算階層(n!)的範例 遞迴方式 int factorial(int n){ if(n <= 1) return 1; 演算法導論，探矽工作室 計算階層(n!)的範例 遞迴方式 int factorial(int n){ if(n <= 1) return 1; return n*factorial(n-1); } 迴圈方式（疊代） int factorial(int n){ int i, num=1; if(n > 1){ for(i = 2; i <= n; i++){ num = num * i; } return num;

演算法導論，探矽工作室 遞迴函式展開之層次

遞迴公式 遞迴結構與遞迴公式 取代方法（substitution method） 支配方法（master method） 演算法導論，探矽工作室 遞迴公式 遞迴結構與遞迴公式 取代方法（substitution method） 支配方法（master method）

遞迴結構(1/2) 解決一個問題時，透過一次又一次重複呼叫自己來處理相關的子問題 演算法導論，探矽工作室 遞迴結構(1/2) 解決一個問題時，透過一次又一次重複呼叫自己來處理相關的子問題 遵循分割處理（divide and conquer，又稱各個擊破）的理念 將問題分割成數個子問題，子問題與原本問題相似但是較小 重複解決子問題 把這些解答合併來建立成原本問題的解答

遞迴結構(2/2) 每一層遞迴中包含的步驟 演算法使用遞迴結構時，他的執行時間通常可以使用一個遞迴公式來描述 演算法導論，探矽工作室 遞迴結構(2/2) 每一層遞迴中包含的步驟 將問題分割（divide）成數個子問題 重複處理（conquer）這些子問題，如果子問題夠小，就用直接計算的方式來解決子問題 將子問題的解答合併（combine）成為原來問題的解答 演算法使用遞迴結構時，他的執行時間通常可以使用一個遞迴公式來描述

遞迴公式 遞迴公式一個方程式或是不等式，可用來描述一個函式與其數值之間的關係 範例 如何分析遞迴公式？ 演算法導論，探矽工作室 遞迴公式 遞迴公式一個方程式或是不等式，可用來描述一個函式與其數值之間的關係 範例 T(n)=aT(n/b)+f(n)，a≧1、b>1，f(n)是指定函數，如O(1)、logn、n、n2等 如何分析遞迴公式？ 取代方法 支配方法

取代方法 就是用重複替代遞迴函數的方式 範例 取代步驟 將遞迴公式一層層地展開、取代，來計算它實際的步驟次數 適用於較單純的遞迴公式 演算法導論，探矽工作室 取代方法 就是用重複替代遞迴函數的方式 將遞迴公式一層層地展開、取代，來計算它實際的步驟次數 適用於較單純的遞迴公式 範例 tRsum(n)=2+tRsum(n-1), n>0且tRsum(0)=2 取代步驟 tRsum(n)=2+tRsum(n-1) =2+2+tRsum(n-2) =4+tRsum(n-2) =..... =2n+ tRsum(0) =2(n+1), n>=0

演算法導論，探矽工作室 支配方法 假設分割處理演算法的整體複雜度是 T(n)而且第一步分割（divide）與第三步合併（combine）所需要的時間複雜度加起來是 f(n)，那麼T(n)滿足下列的遞迴關係： T(n)=aT(n/b)+f(n) 其中T(1)=Θ(1)是很合理的假設，表示只有一筆輸入資料，而演算法需要一個常數時間來解它

演算法導論，探矽工作室 範例： 為方便起見，假設n=4k，k是一個整數，展開遞迴式： 相對應的遞迴樹（recursion tree）表示：

演算法導論，探矽工作室 第一次遞迴

演算法導論，探矽工作室 第二次遞迴

演算法導論，探矽工作室 最後一次遞迴

演算法導論，探矽工作室 推導結果

演算法導論，探矽工作室 考慮一般的狀況 同樣地，為了方便起見，我們假設 n=bk，其中k是一個整數 此遞迴關係式的展開與推導：

由遞迴公式T(n)=aT(n/b)+f(n)所產生的遞迴樹，以及其步驟計次界線關係 演算法導論，探矽工作室 由遞迴公式T(n)=aT(n/b)+f(n)所產生的遞迴樹，以及其步驟計次界線關係

演算法導論，探矽工作室 推導結果 支配理論（master theorem）

支配理論(1/2) 令a ≥ 1且b ≥ 1是兩個常數，f(n)是一個函數，並且假設T(n)滿足下列的遞迴關係 演算法導論，探矽工作室 支配理論(1/2) 令a ≥ 1且b ≥ 1是兩個常數，f(n)是一個函數，並且假設T(n)滿足下列的遞迴關係 T(n)=aT(n/b)+f(n) 1. 如果 ，其中ε是一個大於0的常數，則 2. 如果 ，則 3. 如果 ，其中ε是一個大於0的常數，如果當n夠大時， ，其中c是一個小於1的常數，則

支配理論(2/2) 證明 範例1. T(n) = aT(n/b) + cn 範例2. T(n) = aT(n/b) + cn2 請參閱課本 演算法導論，探矽工作室 支配理論(2/2) 證明 請參閱課本 範例1. T(n) = aT(n/b) + cn T(n) = O(n), if a < b T(n) = O(nlogn), if a = b T(n) = , if a > b 範例2. T(n) = aT(n/b) + cn2 T(n) = O(n2), if a < b2 T(n) = O(n2logn), if a = b2 T(n) = , if a > b2

結論 使用效能分析，可瞭解那個演算法的效能較佳，其理由為何，進而能設計出效能較佳的演算法 演算法導論，探矽工作室 結論 使用效能分析，可瞭解那個演算法的效能較佳，其理由為何，進而能設計出效能較佳的演算法 討論漸進表示法中各種重要的數學表示式，包含了O、Ω、Θ等 瞭解遞迴公式 較單純的遞迴公式可直接用取代方法計算出其複雜度 當遞迴公式的形式為T(n)=aT(n/b)+f(n)的狀況下，使用支配方法引導出的支配理論，讓我們可以計算出較複雜的遞迴公式其複雜度