漸近符號算法

1、漸近符號2.1 漸近符號算法運行時間主要取決于問題的規(guī)模，對于足夠大的輸入，算法運行時間表達式里的那些低階項以及高階項的常數(shù)系數(shù)等，主要受高階項的制約。為了表示算法的漸進有效性，引入漸進符號以便表示算法的運行時間與輸入規(guī)模之間的主要關系，即漸進時間復雜性，來衡量算法的好壞。漸進符號： 、O、 2符號符號: 對于給定的函數(shù) g(n), 記(g(n) = f(n) : 存在三個正常數(shù)c1, c2, n0 ，對于任給nn0，滿足0c1g(n) f(n)c2g(n)的函數(shù)集。并記f(n) =(g(n)，它表示f(n) 是(g(n)中的一個元素。定理：如果 存在，且 則必有f(n) =(g(n)。直觀含

2、義： f(n) 與g(n)同階。3注意： (g(n)的定義要求任意f(n) =(g(n)都是漸進非負的。4例2.1：已知 f (n) = 3n+ 3,證明f (n)= (n).例2.2：已知 f (n) = 1/2n2 - 3n ,證明f (n)= (n2).例2.3：已知 f (n) = 6n3,證明f (n)!=(n2).5幾個結論漸近正函數(shù)的低階項在估計其漸近界的時候可以被忽略掉；對于符號定義中涉及的兩個常數(shù)c1和c2，只要選取c1等于一個比高階項系數(shù)稍小的數(shù)，選取c2等于一個比高階項系數(shù)稍大的數(shù)，就可以滿足符號定義中的不等式；高階項系數(shù)同樣可以忽略，因為它的改變只會使高階項的值發(fā)生常數(shù)

3、系數(shù)倍的改變。例： f(n) = an2 + bn + c， a, b, c 是常數(shù)且 a 0,則必有f(n) = (n2 )。6O符號O符號:對于給定的函數(shù) g(n), 記O(g(n) = f(n) : 存在c和 n0 ，對于任意nn0，滿足0f(n)cg(n)的函數(shù)集。并記f(n) =O(g(n)，它表示f(n) 是O(g(n)中的一個元素。定理：如果 存在，且 則必有f(n) =O(g(n)。直觀含義： f(n) 的階不高于g(n)的階。7注意： O(g(n)的定義要求任意f(n) =O(g(n)都是漸進非負的。8推論：如果f(n) =(g(n) ，則必有f(n) = O(g(n) 。O

4、符號描述了時間復雜度f(n)的上界, 也就是描述算法運行的最壞運行時間。回顧：插入排序算法中主要有2重循環(huán)，for循環(huán)和while循環(huán)，他們最多各執(zhí)行n次，所以最壞運行時間或者說時間復雜度上界為O(n2)。沒有必要計算算法每一行執(zhí)行的時間以及每行執(zhí)行的次數(shù)，然后求和，只需要考慮算法中主要循環(huán)執(zhí)行的次數(shù)即可。9符號符號：對于給定的函數(shù) g(n), 記(g(n) = f(n) : 存在c和 n0 ，對于任意nn0，滿足0cg(n) f(n)的函數(shù)集。并記f(n) = (g(n)，它表示f(n) 是(g(n)中的一個元素。定理：如果 存在，且 則必有f(n) = (g(n)。直觀含義： f(n) 的

5、階不低于g(n)的階。10注意： (g(n)的定義要求任意f(n) = (g(n)都是漸進非負的。11漸進符號的性質(zhì)定理2.1：對于f(n)和g(n), f(n) = (g(n) 當且僅當f(n) = O(g(n) 且 f(n) = (g(n). 證明：由定義即可證得。例：an2 + bn + c = (n2) ，a, b, c均為常數(shù)且a 0, 則必有an2 + bn + c = (n2) ，an2 + bn + c = O(n2).12漸進符號的性質(zhì)定理2.2 ：對于f1(n)和f2(n) , 如果f1(n) =O(g1(n)， f2(n) =O(g2(n) ，則必有f1(n)+ f2(n)= O(maxg1 (n), g2(n) ) 。例： O(n2lgn)+O(n2)=O(n2lgn).推論：對于任意給定