《存在大於零的常数》由会员分享,可在线阅读,更多相关《存在大於零的常数(16页珍藏版)》请在金锄头文库上搜索。
1、Chapter 3Growth of Functions13.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 都成立2範例: 證明 3n2 - 6n = (n2)。證明:為了證明上面的式子,我們必須找到 c1,,c2,和 n0 符合下面的不等式:c1n2 3n2 - 6n c2n2, (對所有 nn0)同除以 n2 得
2、到c1 3 - 6/n c2很明顯地,只要選擇 c1=2,c2=3 以及 n0=6 我們就可以證明 3n2 - 6n = (n2)。得證3註: 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 都成立4(g(n) O(g(n)f(n) = (g(n) 意味著 f(n) = O(g(n)6n
3、 = O(n),6n = O(n2)“執行時間為 O(n2)” 表示 “在最糟的情況下執行時間為 O(n2)”5-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)6tight boundupper boundlower bound7o-notation: f(n) = o(g(n) (litt
4、le-oh of g of n)o(g(n) = f(n)| 對於任何大於零的常數 c,都存在一個常數 n0 0 使得 0 f(n) 0 使得 0 cg(n) =Transitivity,Reflexivity,Symmetry任兩實數皆可互想比較大小(trichotomy),但是任兩函數並不一定能夠互相比較。例如: f(n)=n and g(n)=n1+sin n10Appendix A: Summation formulas1112ExercisesProblem 1:為了解決一個問題而設計程式時,分析該演算法的執行時間複雜度是個很重要的依據。線性時間的演算法通常要比二次方時間的演算法受大
5、家歡迎。通常,問題的大小 n 可以決定演算法的執行時間,也許是要被排序的數字個數,或是多邊形的點的數目,等等。由於要算出一個演算法相對於 n 的執行時間公式不是很容易,如果能夠自動化那就太棒了。很不幸地,一般來說這是不太可能做到的,但是我們在這邊要考慮的程式是非常簡單的,所以把不可能變成了可能。我們的程式是根據下面的規則所建立的(BNF格式),其中 是大於等於零的整數。13Exercises := BEGIN END := | := | := END := LOOP | LOOP n := OP 程式的執行時間可以計算如下:OP-statement 的執行時間就跟它的參數一樣。被 包起來的區段
6、則是會執行很多次,有可能會執行常數次(如果給定的 LOOP 參數是常數),或是執行 n 次(如果給定的 LOOP 參數是 n)。一段 statement 的執行時間只要把構成那段 statement 的全部時間加總起來就是答案。因此程式的執行時間一般來說會跟 n 有關係。14Exercises輸入:第一行會有一個整數 k 表示有幾個程式需要處理。接下來會有 k 個符合之前規則的程式。空白字元以及換行可能會出現在程式中的任何地方,但不會出現在關鍵字或是數字之間,比如 BEGIN, END, LOOP, OP。LOOP 的深度最大只會到 10 。輸出:對於每個程式,第一行先輸出程式的編號,如輸出實
7、例所示。接著要輸出程式的執行時間,這會是一個跟 n 有關的多項式,最大的 degree 只會到 10。用平常表示多項式的方法印出來,格式如下:”Runtime = a*n10+b*n9+ +p*n2+q*n+r”,省略係數是 0 的項次。係數是 1 的話該係數不用寫出來(除了常數項)。如果執行時間是 0,則印出”Runtime = 0”。在每組測資之後印一個空行。15以下是一個輸出入的實例:Sample InputSample Output2BEGINLOOP nOP 4LOOP 3LOOP nOP 1ENDOP 2ENDOP 1ENDOP 17ENDBEGIN OP 1997 LOOP n LOOP n OP 1 END END ENDProgram #1Runtime = 3*n2+11*n+17Program #2Runtime = n2+199716