【正文】 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 當 ?n/2j1? =1， j為最大迭代次數(shù)（或稱最大循環(huán)次數(shù)、或稱最大比較次數(shù)） ?n/2j1?＝ 1 等價于 1≤n/2j1＜ 2 等價于 2j1≤n＜ 2j 等價于（取對數(shù)） j1≤Log2n＜ j 考慮 ?Log2n?≤Log2n＜ ?Log2n ?+1 因為 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 算法運行時間： ? ?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 算法運行時間： ? ?nn lo glo g?kn 22?85 算法 PSUM(Page 23) 輸入： k為正整數(shù) 輸出：對于 1和 n之間的每個完全平方數(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] 算法運行時間： ? ? ? ?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個元素的數(shù)組 A[1..n]（按升序排列）和元素 x。但是，減小空間會導致算法速度的降低是毫無疑問的。一般來說，給算法分配的空間越大，算法運行速度就越快，反之亦然。同理算法 BottomUpSort。同理算法 BinarySearch、 SelectionSort和InsertionSort。 例 1：在算法 LinearSearch中，僅需要一個內存單元保存搜索結果。換句話說，僅僅是算法需要的工作空間。 69 例 （ Page17) f(n)=10n2+20n，求 g(n)，使得 f(n) =Θ(g(n))。 1﹤ log n﹤ n1/2﹤ n﹤ n log n﹤ n2﹤ n3﹤ 2n﹤ n! ?Ｏ 類似于 ≤ ?Ω 類似于 ≥ ?Θ 類似于 ＝ ? o 類似于 ＜ 不要將確切的關系和漸近符號相混淆。 ?67 68 我們用 f(n)﹤ g(n)來表示 f(n)是 o(g(n))的。 f(n)=o(g(n))，當且僅當 f(n)=O(g(n)，但 g(n) ≠O(f(n))。如果對于每一個常數(shù) c0，存在一個自然數(shù) n0，使得 n≥n0 ， f(n)cg(n) 則稱 f(n) = o(g(n)) 。 f(n)=o(g(n))，當且僅當 f(n)=O(g(n))，但 g(n)≠O(f(n))。 表示這二個函數(shù)屬同一復雜性類。 f(n)=Θ(g(n))是一個等價關系，由這個關系導出一個等價類，稱為復雜性類。 解： 當 n≥2， f(n)=3n+2≤3n+n=4n 當 n≥1， f(n)=3n+2≥3n 故當 n≥2，有 3n≤f(n)≤4n 令 g(n)=n，因為當 n≥2時有 3g(n)≤f(n)≤4g(n) 所以 f(n)= Θ(n) 解 2：令 g(n)=n )()(323lim323lim)()(limnnfnnnnngnfnnn???????????????65 Θ符號提供了算法運行時間的精確描述，由于算法InsertionSort的運行時間由線性到平方排列，因此不能用 Θ描述。 ))(()(0)( )(l i m ngnfg nfn ?????? 蘊含著因此若Θ符號定義的一個重要推論： f(n)= Θ(g(n)) 當且僅當 f(n)=O(g(n))并且 g(n)=O(f(n)) 極限是一個正常數(shù)，說明函數(shù) f(n)的增長速度和函數(shù)g(n)的增長速度相差整數(shù)倍，基本為同一級別。 ?Ω 符號定義的一個重要推論： f(n)= Ω(g(n))，當且僅當 g(n)=O(f(n)) 63 ㈣ Θ符號（讀作 theta） 定義 （ Page 16） 令 f(n)和 g(n)是從自然數(shù)集到非負實數(shù)集的二個函數(shù)。無論何時，當排序元素個數(shù)不小于某一個閾值 n0時，運行時間至少是 。 解：令 g(n)=n2 )()(02410lim102410lim)()(lim222nnfnnnnnnngnfnnn?????????????????62 ?在常數(shù)因子范圍內， O符號提供了運行時間上界，而Ω 符號提供了運行時間下界。 解： 當 n0， f(n)=3n+2≥3n。 ))(()(0)( )(lim ngnfng nfn ????? 蘊含著因此若 若極限是一個正常數(shù)，說明函數(shù) f(n)的增長速度和函數(shù) g(n)相差整數(shù)倍，基本為同一級別；若極限為 ∞，說明隨著 n的增大，函數(shù)f(n)增長的速度要比 g(n)快得多。 60 ㈢ Ω符號（讀作 omiga） 定義 （ Page 16） 令 f(n)和 g(n)是從自然數(shù)集到非負實數(shù)集的二個函數(shù)。 解： 當 n≥4，有 n2≤ 2n 故當 n≥4，有 f(n) = 6*2n+n2 ≤ 6*2n + 2n = 7*2n 令 g(n)= 2n ，因為當 n≥4時有 f(n)≤7g(n) 所以 f(n)=O(g(n))=O(2n) ?O符號提供了運行時間的上界； ?算法 InsertionSort執(zhí)行的比較次數(shù)最多為 2（ n(n1)/2 =）， c為某個適當選擇的常數(shù)，則稱該算法的運行時間是 O(n2)。 解 1： 當 n≥2， f(n)=3n+2≤3n+n=4n 令 g(n)=n，當 n≥2時有 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))。 正常數(shù)，可以