Performance Evaluation Office Hour 已公布在課程網站 Performance Evaluation Prof. Michael Tsai 2013/2/26 HW0 is due 23:59 on Thursday. HW1 今天或明天會公布

空間及時間複雜度 程式的空間複雜度: 程式的時間複雜度: 程式執行完畢所需使用的所有空間(記憶體) 程式的時間複雜度: 程式執行完畢所需使用的(執行)時間 Goal: 找出執行時間/使用空間”如何”隨著input size變長 (成長的有多快) 什麼是input size? 問題給的input的”元素數量”, 如: Array大小 多項式最高項的次方 矩陣的長寬 二進位數的位元數目

空間複雜度 程式所需空間: 𝑆 𝑃 =𝑐+ 𝑆 𝑃 (𝐼) 固定的空間 變動的空間 和input/output的大小及內容無關 和待解問題P的某個input instance I(某一個input)有關 隨著input size變大而變大 我們需要注意的地方! 跟recursive function會使用到的額外空間有關 𝑆 𝑃 =𝑐+ 𝑆 𝑃 (𝐼) Ask for examples of the items in 1 and 2. Fixed: instruction space, space for simple variables, fixed-size structured variables, and constants.

Example float abc(float a, float b, float c) { return a+b+b*c+(a+b-c)/(a+b)+4.00; } 𝑆 𝑎𝑏𝑐 𝐼 =? (變動空間) 只有固定空間. 𝑆 𝑎𝑏𝑐 𝐼 =0.

data structure and algorithm I hsin-mu tsai, fall 2010 Example float sum(float list[], int n) { float tempsum=0; int i; for(i=0;i<n;++i) tempsum+=list[i]; return tempsum; } 𝑆 𝑠𝑢𝑚 𝐼 =? (變動空間) 𝑆 𝑠𝑢𝑚 𝐼 =𝑛 (list陣列所占空間)

Example function rsum(float list[], int n) { if (n) return rsum(list,n-1)+list[n-1]; return 0; } 𝑆 𝑟𝑠𝑢𝑚 𝐼 =? (變動空間) list[]占n個sizeof(float)的大小 另外每個recursive call需要紀錄: float *list, int n, 還有return address. 假設這三樣東西需要k bytes (注意是list的指標, 非整個陣列) 𝑆(𝑛)=𝑆’(𝑛)+𝑠𝑖𝑧𝑒𝑜𝑓(𝑓𝑙𝑜𝑎𝑡)∗𝑛 𝑆’ 𝑛 =𝑆’ 𝑛−1 +𝑘 𝑆 ′ 0 =𝑘 𝑆’ 𝑛 =(𝑛+1)𝑘

時間複雜度 一個程式P所需使用的時間: Compile時間: 固定的. (例外?) Run time: Compile所需時間 執行時間 (execution time or run time) How to do it on workstation? Compile時間: 固定的. (例外?) C (and other compiled programming languages)  One Compilation  Multiple Executions Run time: 和input instance的特性有關! 例如input size n - 我們可以把run time寫成T(n) Compile time: fixed  does not depend on instance characteristics (similar to fixed space requirements).

如何得到 𝑇(𝑛)? 總執行時間 所執行的程式指令的數目 & 每個指令的時間 比較數學的方法(使用function來代表程式執行的時間) 花了多少時間? 有其他程式也在使用處理器! 花了多少處理器時間?  跟機器, 作業系統相關 所執行的程式指令的數目 & 每個指令的時間 比較數學的方法(使用function來代表程式執行的時間) Is it good to use? (方法1)

一些小假設 使用一個處理器(processor). 循序一次執行一個指令. (無法同時做超過一件事情) 常用的指令每個指令花固定時間(constant time) +-*/% 記憶體動作(讀取, 修改, 儲存) 控制用的statement: 呼叫subroutine, branch等等

Insertion Sort 藍色: 已經排好的範圍 綠色: 目前正在處理的數字 i 1 2 3 4 5 6 A[i] i 1 2 3 4

Insertion-Sort(A) for j=2 to A Insertion-Sort(A) for j=2 to A.length key=A[j] i=j-1 while i>0 and A[i] > key A[i+1]=A[i] i=i-1 A[i+1]=key 每回合選一個來做insertion 要排的數值是key 從前一個開始看 把比key大的往右邊移 最後把key填入空出來的那一格 j=6 i 1 2 3 4 5 6 A[i]

執行時間=? Insertion-Sort(A) for j=2 to A.length key=A[j] i=j-1 𝑡 𝑖 :j=i的時候那次 while執行次數 n=A.length Insertion-Sort(A) for j=2 to A.length key=A[j] i=j-1 while i>0 and A[i] > key A[i+1]=A[i] i=i-1 A[i+1]=key 時間(cost) 做了幾次 𝑐 1 𝑛 𝑐 2 𝑛−1 𝑐 4 𝑛−1 𝑗=2 𝑛 𝑡 𝑗 𝑐 5 𝑗=2 𝑛 𝑡 𝑗 −1 𝑐 6 𝑗=2 𝑛 𝑡 𝑗 −1 𝑐 7 𝑐 8 𝑛−1 𝑇 𝑛 = 𝑐 1 𝑛+ 𝑐 2 𝑛−1 + 𝑐 4 𝑛−1 + 𝑐 5 𝑗=2 𝑛 𝑡 𝑗 + 𝑐 6 𝑗=2 𝑛 𝑡 𝑗 −1 + 𝑐 7 𝑗=2 𝑛 𝑡 𝑗 −1 + 𝑐 8 (𝑛−1)

Best case 最好的狀況? Best case 全部已經排好了. 𝑡 𝑗 =1, 𝑓𝑜𝑟 𝑗=2,…,𝑛 𝑇 𝑛 = 𝑐 1 𝑛+ 𝑐 2 𝑛−1 + 𝑐 4 𝑛−1 + 𝑐 5 𝑗=2 𝑛 𝑡 𝑗 + 𝑐 6 𝑗=2 𝑛 𝑡 𝑗 −1 + 𝑐 7 𝑗=2 𝑛 𝑡 𝑗 −1 + 𝑐 8 (𝑛−1) = 𝑐 1 + 𝑐 2 + 𝑐 4 + 𝑐 5 + 𝑐 8 𝑛+( 𝑐 2 + 𝑐 4 + 𝑐 5 + 𝑐 8 ) =𝑎𝑛+𝑏 i 1 2 3 4 5 6 A[i]

Worst case 最糟的狀況? Worst case 全部已經排好了. 𝑡 𝑗 =𝑗, 𝑓𝑜𝑟 𝑗=2,…,𝑛 𝑗=2 𝑛 𝑡 𝑗 = 𝑛 𝑛+1 2 −1 𝑗=2 𝑛 𝑡 𝑗 −1= 𝑛 𝑛−1 2 𝑇 𝑛 = 𝑐 1 𝑛+ 𝑐 2 𝑛−1 + 𝑐 4 𝑛−1 + 𝑐 5 𝑗=2 𝑛 𝑡 𝑗 + 𝑐 6 𝑗=2 𝑛 𝑡 𝑗 −1 + 𝑐 7 𝑗=2 𝑛 𝑡 𝑗 −1 + 𝑐 8 (𝑛−1) = 𝑐 5 2 + 𝑐 6 2 + 𝑐 7 2 𝑛 2 + 𝑐 1 + 𝑐 2 + 𝑐 4 + 𝑐 5 2 − 𝑐 6 2 − 𝑐 7 2 + 𝑐 8 𝑛−( 𝑐 2 + 𝑐 4 + 𝑐 5 + 𝑐 8 ) =𝑎 𝑛 2 +𝑏𝑛+𝑐 i 1 2 3 4 5 6 A[i]

Worst case, best case, and average case 最糟的狀況會花的時間(最多時間) 不可能更糟了(確定) Worst case不代表不常發生 (常常發生): 例如 binary search找不到! 很多時候, Average case可能也跟worst case差不了多少 例如: 如果隨意選擇n個數字來做insertion sort 𝑡 𝑗 = 𝑗 2 大概每次會需要移動一半數目的elements 最後算出來還是一個二次方多項式 (quadratic function), 和worst case相同

比較數學的方法—Asymptotic analysis “預測”當input的性質改變(通常是input size改變)時, 執行時間的成長速度(growth of the running time) 比較兩個做相同事情的程式的時間複雜度 “程式步驟”不是那麼精確: “3n+3” 比“3n+5” 快? 通常 “3n+3”, “7n+2”, or “2n+15” 執行時間都相差不遠. 我們將使用一個比較不準確的方式來描述執行時間… 相對的, 如果是3 𝑛 2 +5𝑛+7和10𝑛+50, 𝑛 2 和𝑛就非常重要! "Asymptote" 是漸近線。

Usually no (if the constants are close). Example Usually no (if the constants are close). Program P and Q 𝑇 𝑃 𝑛 = 𝑐 1 𝑛 2 + 𝑐 2 𝑛 𝑇 𝑄 𝑛 = 𝑐 3 𝑛 N很大的時候, Q 會比 P 快, 不管 𝑐 1 , 𝑐 2 , 𝑐 3 的數值是什麼. Example: 𝑐 1 =1, 𝑐 2 =2, 𝑐 3 =100 , then 𝑐 1 𝑛 2 + 𝑐 2 𝑛 2 > 𝑐 3 𝑛 for 𝑛>98. 𝑐 1 =1, 𝑐 2 =2, 𝑐 3 =1000 , then 𝑐 1 𝑛 2 + 𝑐 2 𝑛 2 > 𝑐 3 𝑛 for 𝑛>998. 需要知道 𝑐 1 , 𝑐 2 , 𝑐 3 的數值嗎? No. “小時候胖不算胖” Break even point 𝑇 𝑛 =𝑎 𝑛 2 +𝑏𝑛+𝑐=Θ( 𝑛 2 )

Asymptotic Notation – Big OH Definition [Big “oh”]: 𝑂 𝑔 𝑛 ={𝑓 𝑛 :there exist positive constants 𝑐 and 𝑛 0 such that 0≤𝑓 𝑛 ≤𝑐𝑔 𝑛 for all 𝑛≥ 𝑛 0 } “f of n is big oh of g of n” (是集合的成員) “=“ is “is” not “equal” (“∈”的意思) Ο 𝑔 𝑛 =𝑓(𝑛) 可以想成是Upper Bound (王先生打了太多全壘打, 所以是upper bound)

Example 3𝑛+2=Ο(𝑛) ? Yes, since 3𝑛+2≤4𝑛 for all 𝑛≥2. 3𝑛+3=Ο(𝑛) ? 100𝑛+6=Ο(𝑛) ? Yes, since 100𝑛+6≤101𝑛 for all 𝑛≥10. 10 𝑛 2 +4𝑛+2=Ο( 𝑛 2 ) ? Yes, since 10 n 2 +4n+2≤11 𝑛 2 for all 𝑛≥5. 𝑓 𝑛 ≤𝑐𝑔(𝑛) for all 𝑛,𝑛≥ 𝑛 0

Example 1000 𝑛 2 +100𝑛−6= Ο 𝑛 2 ? Yes, since 1000 𝑛 2 +100𝑛−6≤1001 𝑛 2 for all 𝑛≥100. 6∗ 2 𝑛 + 𝑛 2 = Ο( 2 𝑛 ) ? Yes, since 6∗ 2 𝑛 + 𝑛 2 ≤7∗ 2 n for all 𝑛≥4. 3𝑛+3=Ο( 𝑛 2 ) ? Yes, since 3𝑛+3≤3 𝑛 2 for all 𝑛≥2. 10 𝑛 2 +4𝑛+2=Ο( 𝑛 4 ) ? Yes, since 10 𝑛 2 +4𝑛+2≤10 𝑛 4 for all 𝑛≥2. 3𝑛+2=Ο 1 ? No. Cannot find c and n 0 . 3n<c−2 無法永遠成立. 𝑓 𝑛 ≤𝑐𝑔(𝑛) for all 𝑛,𝑛≥ 𝑛 0

The World of Big Oh Ο 1 constant Ο 𝑛 linear Ο 𝑛 2 quadratic Ο 𝑛 3 cubic Ο 2 𝑛 exponential Ο 1 ,Ο log 𝑛 , Ο 𝑛 , Ο 𝑛log 𝑛 , Ο 𝑛 2 , Ο 𝑛 3 , Ο 2 𝑛 Faster Slower

On a 1 billion-steps-per-sec computer 𝒏 𝒏 𝒍𝒐 𝒈 𝟐 𝒏 𝒏 𝟐 𝒏 𝟑 𝒏 𝟒 𝒏 𝟏𝟎 𝟐 𝒏 10 .01𝜇𝑠 .03𝜇𝑠 .1𝜇𝑠 1𝜇𝑠 10𝜇𝑠 10𝑠 20 .02𝜇𝑠 .09𝜇𝑠 .4𝜇𝑠 8𝜇𝑠 160𝜇𝑠 2.84ℎ 1𝑚𝑠 30 .15𝜇𝑠 .9𝜇𝑠 27𝜇𝑠 810𝜇𝑠 6.83𝑑 1𝑠 40 .04𝜇𝑠 .21𝜇𝑠 1.6𝜇𝑠 64𝜇𝑠 2.56𝑚𝑠 121𝑑 18𝑚 50 .05𝜇𝑠 .28𝜇𝑠 2.5𝜇𝑠 125𝜇𝑠 6.25𝑚𝑠 3.1𝑦 13𝑑 100 .10𝜇𝑠 .66𝜇𝑠 100𝑚𝑠 3171𝑦 4∗ 10 13 𝑦 10 3 9.96𝜇𝑠 16.67𝑚 3.17∗ 10 13 𝑦 32∗ 10 283 𝑦 10 4 130𝜇𝑠 115.7𝑑 3.17∗ 10 23 𝑦 10 5 100𝜇𝑠 1.66𝑚𝑠 11.57𝑑 3.17∗ 10 33 𝑦 10 6 19.92𝑚𝑠 31.71𝑦 3.17∗ 10 7 𝑦 3.17∗ 10 43 𝑦

Big Oh 是 Upper Bound 但是沒有說它是多好的upper bound 𝑛=Ο(𝑛) 𝑛=Ο( 𝑛 2 ) 𝑛=Ο( 𝑛 2.5 ) 𝑛=Ο( 2 𝑛 ) 通常我們會把它取得越小(緊)越好. 3𝑛+3=Ο( 𝑛 2 ) 3𝑛+3=Ο 𝑛

一些條件 正式的定義下, O(g(n))裡面的n為自然數={0,1,2,…} O(g(n))的member f(n)必須為asymptotically nonnegative (也就是當n很大的時候, f(n)必須不為負) g(n)本身也必須為asymptotically nonnegative 以上也適用於其他的asymptotic notation!

A Useful Theorem Theorem: If 𝑓 𝑛 = 𝒂 𝒎 𝒏 𝒎 +…+ 𝑎 1 𝑛+ 𝑎 0 , then 𝑓 𝑛 =Ο( 𝒏 𝒎 ). Proof: 𝑓 𝑛 ≤ 𝑖=0 𝑚 𝑎 𝑖 𝑛 𝑖 = 𝑛 𝑚 𝑖=0 𝑚 𝑎 𝑖 𝑛 𝑖−𝑚 ≤ 𝑛 𝑚 𝑖=0 𝑚 𝑎 𝑖 , for all 𝑛≥1. So, 𝑓 𝑛 =Ο 𝑛 𝑚 . 0≤𝑛 𝑖−𝑚 ≤1

Asymptotic Notation – Omega Definition [Omega]: Ω 𝑔 𝑛 ={𝑓(𝑛): there exist positive constants 𝑐 and 𝑛 0 such that 0≤𝑐𝑔 𝑛 ≤𝑓(𝑛) for all 𝑛≥ 𝑛 0 } 𝑓 𝑛 =Ω 𝑔 𝑛 “f of n is omega of g of n” 可以想成是Lower Bound

Examples 3𝑛+2=Ω 𝑛 since 3𝑛+2≥3𝑛 for all 𝑛≥1. 3𝑛+3=Ω(𝑛) 100𝑛+6=Ω(𝑛) since 100𝑛+6≥100𝑛 for all 𝑛≥1. 10 𝑛 2 +4𝑛+2=Ω( 𝑛 2 ) since 10 n 2 +4n+2≥ 𝑛 2 for all 𝑛≥1. 6∗ 2 𝑛 + 𝑛 2 =Ω( 2 𝑛 ) since 6∗ 2 𝑛 + 𝑛 2 ≥ 2 n for all 𝑛≥1. 𝑓 𝑛 ≥𝑐𝑔(𝑛) for all 𝑛,𝑛≥ 𝑛 0

Examples 3𝑛+3=Ω(1) 10 𝑛 2 +4𝑛+2=Ω(1) 6∗ 2 𝑛 + 𝑛 2 =Ω 𝑛 100 6∗ 2 𝑛 + 𝑛 2 =Ω 𝑛 100 6∗ 2 𝑛 + 𝑛 2 =Ω 𝑛 50.2 6∗ 2 𝑛 + 𝑛 2 =Ω 𝑛 2 6∗ 2 𝑛 + 𝑛 2 =Ω 𝑛 6∗ 2 𝑛 + 𝑛 2 =Ω 1 𝑓 𝑛 ≥𝑐𝑔(𝑛) for all 𝑛,𝑛≥ 𝑛 0

Discussion Omega is a lower bound. Should be as large a function as possible. Theorem: If 𝑓 𝑛 = 𝑎 𝑚 𝑛 𝑚 +…+ 𝑎 1 𝑛+ 𝑎 0 and 𝑎 𝑚 >0, then 𝑓 𝑛 =Ω( 𝑛 𝑚 ). (證明: 請自己證證看!)

Asymptotic Notation – Theta Definition [Theta]: Θ 𝑔 𝑛 = {𝑓(𝑛): there exist positive constants 𝑐 1 , 𝑐 2 , 𝑛 0 such that 0≤ 𝑐 1 𝑔 𝑛 ≤𝑓 𝑛 ≤ 𝑐 2 𝑔 𝑛 for all 𝑛≥ 𝑛 0 } 𝑓(𝑛)=Θ 𝑔 𝑛 “f of n is theta of g of n” 三明治夾心, 同時具有𝑂(𝑔(𝑛)和Ω 𝑔 𝑛 (Asymptotically tight) Theta Platform GMC Terrain

用圖表示 Big Oh 紅色 Omega 藍色 Theta 紅色藍色都要

Example c 1 g(n)≥𝑓 𝑛 ≥ 𝑐 2 𝑔(𝑛) for all 𝑛,𝑛≥ 𝑛 0 3𝑛+2=Θ 𝑛 since 3𝑛+2≥3𝑛 for all 𝑛≥2 and 3𝑛+2≤4𝑛 for all 𝑛≥2. 3𝑛+3=Θ(𝑛) 10 𝑛 2 +4𝑛+2=Θ( 𝑛 2 ) 6∗ 2 𝑛 + 𝑛 2 =Θ( 2 𝑛 ) 10∗ log 𝑛 +4=Θ log 𝑛 3𝑛+2≠Θ 1 3𝑛+3≠Θ 𝑛 2 10 𝑛 2 +4𝑛+2≠Θ 𝑛 10 𝑛 2 +4𝑛+2≠Θ 1 6∗ 2 𝑛 + 𝑛 2 ≠Θ( 𝑛 2 ) 6∗ 2 𝑛 + 𝑛 2 ≠Θ 𝑛 100 6∗ 2 𝑛 + 𝑛 2 ≠Θ 1 c 1 g(n)≥𝑓 𝑛 ≥ 𝑐 2 𝑔(𝑛) for all 𝑛,𝑛≥ 𝑛 0

Discussion More precise than both the “big oh” and omega notations It is true if and only g(n) is both an upper and lower bound on f(n). g(n) is an asymptotically tight bound for f(n) if f(n)=Θ(𝑛) 意思是說, f(n) equals g(n) within a constant factor (差常數倍而已). Theorem: If 𝑓 𝑛 = 𝑎 𝑚 𝑛 𝑚 +…+ 𝑎 1 𝑛+ 𝑎 0 and 𝑎 𝑚 >0, then 𝑓 𝑛 =Θ( 𝑛 𝑚 ). (證明: 請自己證證看!)

O (小歐) & 𝜔 (小歐美加) o 𝑔 𝑛 ={𝑓 𝑛 :for any positive constant 𝑐, there exists a constant 𝑛 0 such that 0≤𝑓 𝑛 <𝑐𝑔 𝑛 for all 𝑛≥ 𝑛 0 } 意思是g(n)是f(n)不緊的upper bound (長得比f(n)快) 也就是, lim 𝑛→∞ 𝑓 𝑛 𝑔 𝑛 =0 𝜔 𝑔 𝑛 ={𝑓(𝑛): for any positive constant 𝑐, there exists a constant 𝑛 0 such that 0≤𝑐𝑔 𝑛 <𝑓(𝑛) for all 𝑛≥ 𝑛 0 } 意思是g(n)是f(n)不緊的lower bound (長得比f(n)慢) 也就是, lim 𝑛→∞ 𝑓 𝑛 𝑔 𝑛 =∞

等式與不等式 𝑛=𝑂( 𝑛 2 ) (這個是什麼意思我們懂) 2 𝑛 2 +3𝑛+1=2 𝑛 2 +Θ(𝑛) (????) 2 𝑛 2 +3𝑛+1=2 𝑛 2 +Θ(𝑛) (????) 意思是 2 𝑛 2 +3𝑛+1=2 𝑛 2 +f(n), 然後 f(n)= Θ 𝑛 2 𝑛 2 +Θ 𝑛 =Θ( 𝑛 2 ) (???) 不管左邊asymptotic notation代表的function怎麼選擇, 一定有一種方法選擇右邊的asymptotic notation代表的function使得等號成立. 2 𝑛 2 +3𝑛+1=2 𝑛 2 +Θ 𝑛 =Θ( 𝑛 2 ) (???)

Another Example int binsearch(int list[], int searchnum, int left, int right) { int middle; while(left<=right) { middle=(left+right)/2; switch(COMPARE(list[middle], searchnum)) { case -1: left=middle+1; break; case 0: return middle; case 1: right=middle-1; } return -1;

Worst case: Θ log 𝑛 Best case: Θ 1 1 3 4 4 6 7 11 13 13 13 18 19 searchnum=13; 1 2 3 4 5 6 7 8 9 10 11 1 3 4 4 6 7 11 13 13 13 18 19 left right middle middle=(left+right)/2; (floor function) what if it is a cell function? middle=(left+right)/2; left=middle+1; Half the searching window every iteration.

Another Example: recursive binsearch int binsearch(int list[], int searchnum, int left, int right) { int middle; if (left<=right) { middle=(left+right)/2; switch(COMPARE(list[middle], searchnum)) { case -1: return binsearch(list, searchnum, middle+1, right) case 0: return middle; case 1: return binsearch(list, searchnum, left, middle-1) } } else return -1; } T 𝑛 =𝑇 𝑛 2 +𝑂(1) T 1 =𝑂 1 , 𝑇 0 =𝑂(1) T 𝑛 =𝑇 𝑛 2 +𝑐= 𝑇 𝑛 4 +𝑐 +𝑐=…=𝑇 1 +𝑐 (𝑛 log 𝑛) T 𝑛 =𝑂(𝑛 log 𝑛)

演算法東西軍: 兜基?? Θ( 𝑛 2 ) Θ(𝑛) 𝑛 2 ms 10 6 𝑛 𝑚𝑠

哪一個好… Θ( 𝑛 2 ) Θ(𝑛) 𝑛 2 ms 10 6 𝑛 𝑚𝑠 n很大的時候右邊比左邊好 但是n會很大嗎? 有時候不會 10 6 𝑛 𝑚𝑠 n很大的時候右邊比左邊好 但是n會很大嗎? 有時候不會 如果n永遠小於 10 6 ?? 結論:要看n大小 (實際上寫程式的時候適用)

Reading Assignments Cormen 2.1, 2.2, 3.1