1、Chapter 3,Growth of Functions,Growth of Functions,2,3.1 Asymptotic notation -notation: f(n) = (g(n)，g(n) is an asymptotically tight bound for f(n)。 (g(n) = f(n)| 存在大於零的常數(shù) c1，c2，以及 n0 使得 0 c1 g(n) f(n) c2 g(n) 對於所有的 n n0 都成立,Growth of Functions,3,範(fàn)例: 證明 3n2 - 6n = (n2)。 證明: 為了證明上面的式子，我們必須找到 c1,，c2，和

2、n0 符合下面的不等式： c1n2 3n2 - 6n c2n2， (對所有 nn0) 同除以 n2 得到 c1 3 - 6/n c2 很明顯地，只要選擇 c1=2，c2=3 以及 n0=6 我們就可以證明 3n2 - 6n = (n2)。 得證,Growth of Functions,4,註： 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)| 存在大於零的常數(shù) c and n0

3、 使得 0 f(n) c2 g(n) 對於所有的 n n0 都成立,Growth of Functions,5,(g(n) O(g(n) f(n) = (g(n) 意味著 f(n) = O(g(n) 6n = O(n)，6n = O(n2) “執(zhí)行時(shí)間為 O(n2)” 表示 “在最糟的情況下執(zhí)行時(shí)間為 O(n2)”,Growth of Functions,6,-notation: f(n) = (g(n)，g(n) is an asymptotically lower bound for f(n)。 (g(n) = f(n)| 存在大於零的常數(shù) c 和 n0 使得 0 cg(n) f(n) 對

4、於所有 n n0 都成立 註： f(n) = (g(n) 若且唯若 (f(n)=O(g(n) & (f(n)= (g(n),Growth of Functions,7,tight bound,upper bound,lower bound,Growth of Functions,8,o-notation: f(n) = o(g(n) (little-oh of g of n) o(g(n) = f(n)| 對於任何大於零的常數(shù) c，都存在一個(gè)常數(shù) n0 0 使得 0 f(n) cg(n) 對於所有的 n n0 都成立 2n = o(n2)，但是 2n2 o(n2) f(n) = o(g(n)

5、也可以被定義成,Growth of Functions,9,-notation: f(n) = (g(n) (little-omega of g of n) (g(n) = f(n)| 對於任何大於零的常數(shù) c，都存在一個(gè)常數(shù) n0 0 使得 0 cg(n) f(n) 對於所有 n n0 都成立 2n2 = (n)，但是 2n2 (n2) f(n) = (g(n) 若且唯若,Growth of Functions,10,Comparison of functions 函數(shù):Oo 實(shí)數(shù):= Transitivity，Reflexivity，Symmetry 任兩實(shí)數(shù)皆可互想比較大小(tricho

6、tomy)，但是任兩函數(shù)並不一定能夠互相比較。 例如： f(n)=n and g(n)=n1+sin n,Growth of Functions,11,Appendix A: Summation formulas,Growth of Functions,12,Growth of Functions,13,Exercises,Problem 1: 為了解決一個(gè)問題而設(shè)計(jì)程式時(shí)，分析該演算法的執(zhí)行時(shí)間複雜度是個(gè)很重要的依據(jù)。線性時(shí)間的演算法通常要比二次方時(shí)間的演算法受大家歡迎。 通常，問題的大小 n 可以決定演算法的執(zhí)行時(shí)間，也許是要被排序的數(shù)字個(gè)數(shù)，或是多邊形的點(diǎn)的數(shù)目，等等。由於要算出一個(gè)演算

7、法相對於 n 的執(zhí)行時(shí)間公式不是很容易，如果能夠自動(dòng)化那就太棒了。很不幸地，一般來說這是不太可能做到的，但是我們在這邊要考慮的程式是非常簡單的，所以把不可能變成了可能。我們的程式是根據(jù)下面的規(guī)則所建立的（BNF格式），其中 是大於等於零的整數(shù)。,Growth of Functions,14,Exercises, := BEGIN END := | := | := END := LOOP | LOOP n := OP 程式的執(zhí)行時(shí)間可以計(jì)算如下：OP-statement 的執(zhí)行時(shí)間就跟它的參數(shù)一樣。被 包起來的區(qū)段則是會(huì)執(zhí)行很多次，有可能會(huì)執(zhí)行常數(shù)次（如果給定的 LOOP 參數(shù)是常數(shù)），或是執(zhí)行

8、 n 次（如果給定的 LOOP 參數(shù)是 n）。一段 statement 的執(zhí)行時(shí)間只要把構(gòu)成那段 statement 的全部時(shí)間加總起來就是答案。因此程式的執(zhí)行時(shí)間一般來說會(huì)跟 n 有關(guān)係。,Growth of Functions,15,Exercises,輸入：第一行會(huì)有一個(gè)整數(shù) k 表示有幾個(gè)程式需要處理。接下來會(huì)有 k 個(gè)符合之前規(guī)則的程式?？瞻鬃衷约皳Q行可能會(huì)出現(xiàn)在程式中的任何地方，但不會(huì)出現(xiàn)在關(guān)鍵字或是數(shù)字之間，比如 BEGIN, END, LOOP, OP。LOOP 的深度最大只會(huì)到 10 。 輸出：對於每個(gè)程式，第一行先輸出程式的編號，如輸出實(shí)例所示。接著要輸出程式的執(zhí)行時(shí)間，這會(huì)是一個(gè)跟 n 有關(guān)的多項(xiàng)式，最大的 degree 只會(huì)到 10。用平常表示多項(xiàng)式的方法印出來，格式如下： ”Runtime = a*n10+b*