Growth of Functions 我們要如何知道一個演算法的優劣？ 要如何分辨兩個演算法何者較佳？ 在這個章節中將介紹一些表示法，今後都將用本章所介紹的表示法來表示演算法的時間複雜度。

3.1 Asymptotic notation Θ-notation: f(n) = Θ(g(n))，g(n) is an asymptotically tight bound for f(n)。 Θ(g(n)) = {f(n)| 存在大於零的常數 c1，c2，以及 n0 使得 0  c1 g(n)  f(n)  c2 g(n) 對於所有的 n  n0 都成立} 假設有個演算法的執行時間為Θ(n2)， 我們可以說：當 n 大到某個程度之後，所需要的執行時間會跟 n2 成正比。 Growth of Functions

為了證明上面的式子，我們必須找到 c1,，c2，和 n0 符合下面的不等式： 範例: 證明 3n2 - 6n = Θ(n2)。 證明: 為了證明上面的式子，我們必須找到 c1,，c2，和 n0 符合下面的不等式： c1n2  3n2 - 6n  c2n2， (對所有 nn0) 同除以 n2 得到 c1  3 - 6/n  c2 很明顯地，只要選擇 c1=2，c2=3 以及 n0=6 我們就可以證明 3n2 - 6n = Θ(n2)。 得證 Growth of Functions

註： f(n) = Θ(g(n)) 若且唯若 g(n)= Θ(f(n))，例如: n2=(3n2-6n) O-notation: f(n) = O(g(n))，g(n) is an asymptotically upper bound for f(n)。 O(g(n)) = {f(n)| 存在大於零的常數 c and n0 使得 0  f(n)  c2 g(n) 對於所有的 n  n0 都成立} O(n2)的意義是說：當 n 大到某個程度之後，所需要花的時間””最慘””只會跟 n2 成正比。 Growth of Functions

f(n) = Θ(g(n)) 意味著 f(n) = O(g(n)) 6n = O(n)，6n = O(n2) Θ(g(n))  O(g(n)) f(n) = Θ(g(n)) 意味著 f(n) = O(g(n)) 6n = O(n)，6n = O(n2) “執行時間為 O(n2)” 表示 “在最糟的情況下執行時間為 O(n2)” Growth of Functions

Ω(g(n)) = {f(n)| 存在大於零的常數 c 和 n0 使得 0  cg(n)  f(n) 對於所有 n  n0 都成立} Ω-notation: f(n) = Ω(g(n))，g(n) is an asymptotically lower bound for f(n)。 Ω(g(n)) = {f(n)| 存在大於零的常數 c 和 n0 使得 0  cg(n)  f(n) 對於所有 n  n0 都成立} 註： f(n) = Θ(g(n)) 若且唯若 (f(n)=O(g(n))) & (f(n)=Ω (g(n))) Ω(n2)的意義則是：當 n 大到某個程度之後，所需要花的時間””至少””會跟 n2 成正比。 Growth of Functions

tight bound upper bound lower bound Growth of Functions 用函式的圖形來表示剛剛介紹的三種表示法。 Θ是tight bound，O是upper bound， Ω是lower bound。 tight bound upper bound lower bound Growth of Functions

o-notation: f(n) = o(g(n)) (little-oh of g of n) o(g(n)) = {f(n)| 對於任何大於零的常數 c，都存在一個常數 n0 > 0 使得 0  f(n) < cg(n) 對於所有的 n  n0 都成立} 2n = o(n2)，但是 2n2  o(n2) f(n) = o(g(n)) 也可以被定義成 Growth of Functions

ω-notation: f(n) = ω(g(n)) (little-omega of g of n) ω(g(n)) = {f(n)| 對於任何大於零的常數 c，都存在一個常數 n0 > 0 使得 0  cg(n) < f(n) 對於所有 n  n0 都成立} 2n2 = ω(n)，但是 2n2  ω(n2) f(n) = ω(g(n)) 若且唯若 Growth of Functions

Comparison of functions 函數: ω Ω Θ O o 實數: >  =  < Transitivity，Reflexivity，Symmetry 任兩實數皆可互想比較大小(trichotomy)，但是任兩函數並不一定能夠互相比較。 例如： f(n)=n and g(n)=n1+sin n f(n)=n g(n)=n1+sin(n) 在某些時候 f(n) 比較大，某些時候 g(n) 比較大 Growth of Functions

Appendix A: Summation formulas 一些分析常用到的數學公式 Growth of Functions

Growth of Functions

Exercises Problem 1: 為了解決一個問題而設計程式時，分析該演算法的執行時間複雜度是個很重要的依據。線性時間的演算法通常要比二次方時間的演算法受大家歡迎。 通常，問題的大小 n 可以決定演算法的執行時間，也許是要被排序的數字個數，或是多邊形的點的數目，等等。由於要算出一個演算法相對於 n 的執行時間公式不是很容易，如果能夠自動化那就太棒了。很不幸地，一般來說這是不太可能做到的，但是我們在這邊要考慮的程式是非常簡單的，所以把不可能變成了可能。我們的程式是根據下面的規則所建立的（BNF格式），其中 <number> 是大於等於零的整數。 Growth of Functions

Exercises <Program> ::= "BEGIN" <Statementlist> "END" <Statementlist> ::= <Statement> | <Statement> <Statementlist> <Statement> ::= < LOOP-Statement> | <OP-Statement> <LOOP-Statement> ::= <LOOP-Header> <Statementlist> "END" <LOOP-Header> ::= "LOOP" <number> | "LOOP n" <OP-Statement> ::= "OP" <number> 程式的執行時間可以計算如下：OP-statement 的執行時間就跟它的參數一樣。被 <LOOP-Statement> 包起來的區段則是會執行很多次，有可能會執行常數次（如果給定的 LOOP 參數是常數），或是執行 n 次（如果給定的 LOOP 參數是 n）。一段 statement 的執行時間只要把構成那段 statement 的全部時間加總起來就是答案。因此程式的執行時間一般來說會跟 n 有關係。 Growth of Functions

Exercises 輸入：第一行會有一個整數 k 表示有幾個程式需要處理。接下來會有 k 個符合之前規則的程式。空白字元以及換行可能會出現在程式中的任何地方，但不會出現在關鍵字或是數字之間，比如 BEGIN, END, LOOP, OP。LOOP 的深度最大只會到 10 。 輸出：對於每個程式，第一行先輸出程式的編號，如輸出實例所示。接著要輸出程式的執行時間，這會是一個跟 n 有關的多項式，最大的 degree 只會到 10。用平常表示多項式的方法印出來，格式如下： ”Runtime = a*n^10+b*n^9+ …+p*n^2+q*n+r”，省略係數是 0 的項次。係數是 1 的話該係數不用寫出來（除了常數項）。如果執行時間是 0，則印出”Runtime = 0”。在每組測資之後印一個空行。 Growth of Functions

以下是一個輸出入的實例: Sample Input Sample Output 2 BEGIN LOOP n OP 4 LOOP 3 END OP 2 OP 17 BEGIN OP 1997 LOOP n LOOP n OP 1 END END END Program #1 Runtime = 3*n^2+11*n+17 Program #2 Runtime = n^2+1997 Growth of Functions