【正文】 O(n2)。 ))(()(0)( )(lim ngnfng nfn ????? 蘊(yùn)含著因此若 若極限是一個(gè)正常數(shù)，說明函數(shù) f(n)的增長速度和函數(shù) g(n)相差整數(shù)倍，基本為同一級(jí)別；若極限為 ∞，說明隨著 n的增大，函數(shù)f(n)增長的速度要比 g(n)快得多。 解：令 g(n)=n2 )()(02410lim102410lim)()(lim222nnfnnnnnnngnfnnn?????????????????62 ?在常數(shù)因子范圍內(nèi)， O符號(hào)提供了運(yùn)行時(shí)間上界，而Ω 符號(hào)提供了運(yùn)行時(shí)間下界。 ?Ω 符號(hào)定義的一個(gè)重要推論： f(n)= Ω(g(n))，當(dāng)且僅當(dāng) g(n)=O(f(n)) 63 ㈣ Θ符號(hào)（讀作 theta） 定義 （ Page 16） 令 f(n)和 g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。 解： 當(dāng) n≥2， f(n)=3n+2≤3n+n=4n 當(dāng) n≥1， f(n)=3n+2≥3n 故當(dāng) n≥2，有 3n≤f(n)≤4n 令 g(n)=n，因?yàn)楫?dāng) n≥2時(shí)有 3g(n)≤f(n)≤4g(n) 所以 f(n)= Θ(n) 解 2：令 g(n)=n )()(323lim323lim)()(limnnfnnnnngnfnnn???????????????65 Θ符號(hào)提供了算法運(yùn)行時(shí)間的精確描述，由于算法InsertionSort的運(yùn)行時(shí)間由線性到平方排列，因此不能用 Θ描述。 表示這二個(gè)函數(shù)屬同一復(fù)雜性類。如果對(duì)于每一個(gè)常數(shù) c0，存在一個(gè)自然數(shù) n0，使得 n≥n0 ， f(n)cg(n) 則稱 f(n) = o(g(n)) 。 ?67 68 我們用 f(n)﹤ g(n)來表示 f(n)是 o(g(n))的。 69 例 （ Page17) f(n)=10n2+20n，求 g(n)，使得 f(n) =Θ(g(n))。 例 1：在算法 LinearSearch中，僅需要一個(gè)內(nèi)存單元保存搜索結(jié)果。同理算法 BottomUpSort。但是，減小空間會(huì)導(dǎo)致算法速度的降低是毫無疑問的。 1. low←1 : high←n : j←0 //j=0表示未找到 2. while (low≤high) and (j＝ 0) 3. mid← ?(low+high)/2? //? ?表示向下 取整 (Page 45) 4. if x＝ A[mid] then j←mid 5. else 6. if x＜ A[mid] then high←mid 1 7. else low←mid+1 //x＞ A[mid] 8. end if 9. end if 10. end while 11. return j 79 當(dāng) ?n/2j1? =1， j為最大迭代次數(shù)（或稱最大循環(huán)次數(shù)、或稱最大比較次數(shù)） ?n/2j1?＝ 1 等價(jià)于 1≤n/2j1＜ 2 等價(jià)于 2j1≤n＜ 2j 等價(jià)于（取對(duì)數(shù)） j1≤Log2n＜ j 考慮 ?Log2n?≤Log2n＜ ?Log2n ?+1 因?yàn)?j是整數(shù)，故有 j1＝ ?Log2n ? 或 j＝ ?Log2n ?+1 二者均有 j＝ ?Log2n ?+1 80 算法 SelectionSort（參見 Page 8） 輸入：數(shù)組 A[1..n] 輸出：按升序排列的數(shù)組 A[1..n] 1. for i←1 to n 1 2. k←i 3. for j←i+1 to n 4. if A[j]A[k] then k←j 5. end for 6. if k≠i then 交換 A[i]和 A[k] 7. end for 81 算法 InsertionSort(參見 Page 89) 輸入：數(shù)組 A[1..n] 輸出：按升序排列的數(shù)組 A[1..n] 1. for i←2 to n 2. x←A [i] 3. j←i 1 4. while (j0) and (A[j]x) 5. A[j+1]←A[j] 6. j←j 1 7. end while 8. A[j+1]←x 9. end for 82 算法 InsertionSort(參見 Page 89) 輸入：數(shù)組 A[1..n] 輸出：按升序排列的數(shù)組 A[1..n] 1. for i←2 to n 2. x←A [i] 3. j←i 1 4. while (j0) and (A[j]x) 5. A[j+1]←A[j] 6. j←j 1 7. end while 8. A[j+1]←x 9. end for 83 算法 COUNT1(Page 21) 輸入： n=2k,k為正整數(shù) 輸出：執(zhí)行次數(shù) count 1. count ←0 2. while n≥1 3. for j←1 to n 4. count ← count +1 5. end for 6. n ←n/2 7. end while 8. return count 算法運(yùn)行時(shí)間： ? ?nnP a g ennnkkjjkjj?????????? ??? ????12))(50(212212 0084 算法 COUNT3(Page 2223) 輸入： k為正整數(shù) 輸出：執(zhí)行次數(shù) count 1. count ←0 2. for i←1 to n 3. j← 2 4. while j≤n 5. j← j2 6. count ← count +1 7. end while 7. end for 8. return count 算法運(yùn)行時(shí)間： ? ?nn lo glo g?kn 22?85 算法 PSUM(Page 23) 輸入： k為正整數(shù) 輸出：對(duì)于 1和 n之間的每個(gè)完全平方數(shù) j，輸出 1. 2. for j←1 to k 3. sum[j]← 0 4. for i←1 to j2 5. j← j2 6. sum[j]← sum[j] + i 7. end for 7. end for 8. return sum[1…k] 算法運(yùn)行時(shí)間： ? ? ? ?126)12)(1( nkkkkjkj?????????2kn???jii1nk ?。 1. j←1 2. while (jn) and (x≠A[j]) 3. j←j+1 4. end while 5. if x=A[j] then return j else return 0 78 算法 BinarySearch（ Page 4） 輸入： n個(gè)元素的數(shù)組 A[1..n]（按升序排列）和元素 x。一般來說，給算法分配的空間越大，算法運(yùn)行速度就越快，反之亦然。同理算法 BinarySearch、 SelectionSort和InsertionSort。換句話說，僅僅是算法需要的工作空間。 1﹤ log n﹤ n1/2﹤ n﹤ n log n﹤ n2﹤ n3﹤ 2n﹤ n! ?Ｏ 類似于 ≤ ?Ω 類似于 ≥ ?Θ 類似于 ＝ ? o 類似于 ＜ 不要將確切的關(guān)系和漸近符號(hào)相混淆。 f(n)=o(g(n))，當(dāng)且僅當(dāng) f(n)=O(g(n)，但 g(n) ≠O(f(n))。 f(n)=o(g(n))，當(dāng)且僅當(dāng) f(n)=O(g(n))，但 g(n)≠O(f(n))。 f(n)=Θ(g(n))是一個(gè)等價(jià)關(guān)系，由這個(gè)關(guān)系導(dǎo)出一個(gè)等價(jià)類，稱為復(fù)雜性類。 ))(()(0)( )(l i m ngnfg nfn ?????? 蘊(yùn)含著因此若Θ符號(hào)定義的一個(gè)重要推論： f(n)= Θ(g(n)) 當(dāng)且僅當(dāng) f(n)=O(g(n))并且 g(n)=O(f(n)) 極限是一個(gè)正常數(shù)，說明函數(shù) f(n)的增長速度和函數(shù)g(n)的增長速度相差整數(shù)倍，基本為同一級(jí)別。無論何時(shí)，當(dāng)排序元素個(gè)數(shù)不小于某一個(gè)閾值 n0時(shí)，運(yùn)行時(shí)間至少是 。 解： 當(dāng) n0， f(n)=3n+2≥3n。 60 ㈢ Ω符號(hào)（讀作 omiga） 定義 （ Page 16） 令 f(n)和 g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的二個(gè)函數(shù)。 解 1： 當(dāng) n≥2， f(n)=3n+2≤3n+n=4n 令 g(n)=n，當(dāng) n≥2時(shí)有 f(n)≤4g(n) ∵ f(n)≤4g(n) ∴ f(n)=O(g(n))=O(n) 解 2：令 g(n)=n )()(23lim323lim)()(limnOnfnnnnngnfnnn???????????????同理可證： f(n)=O(nk)， k≥1（ g(n)通常為上限最小值，即 k=1） 58 例 2： f(n)=10n2+4n+2，求 g(n)，使得 f(n)=O(g(n))。如果存在一個(gè)自然數(shù) n0和一個(gè)正常數(shù) c，使得 n≥n0 ， f(n)≤cg(n) 則稱 f(n)=O(g(n))， n0稱為閾值 。漸近運(yùn)行時(shí)間通常稱為時(shí)間復(fù)雜性。因?yàn)楫?dāng)很大時(shí)低階項(xiàng)便顯得不太重要。 54 為了簡化對(duì)算法過程的分析，常常會(huì)忽略算法中每條語句的真實(shí)代價(jià)，而用常量 ci表示。 ③算法應(yīng)獨(dú)立于機(jī)器，無論科技如何進(jìn)步，對(duì)算法運(yùn)行時(shí)間的評(píng)估始終成立。 執(zhí)行算法 BottomUpSort的最大比較次數(shù) nlog2nn+1 執(zhí)行