【正文】 77 如何估計算法運行時間 通過計算迭代次數(shù)估計算法運行時間 算法 LinearSearch（ Page 3） 輸入： n個元素的數(shù)組 A[1..n]和元素 x 輸出：如果 x=A[j]（ 1≤j≤n），則輸出 j，否則輸出 0。如果加上局部變量，可以得出需要的空間數(shù)量為 Θ(1)。用該記號可簡明地表示復雜性的層次 。 ㈤ o符號（讀作小 o） 由等價關系 f(n)=Θ(g(n)) 導出了一個等價類，為了說明二個函數(shù)屬于不同類，引入了 o符號。如果存在一個自然數(shù) n0和二個正常數(shù) c1和 c2，使得 n≥n0 ， c1g(n)≤f(n)≤c2g(n) 則稱 f(n)= Θ(g(n))， n0稱為閾值 。 可以是正常數(shù)或 ∞ ?61 例 1： f(n)=3n+2，求 g(n)，使得 f(n)=Ω(g(n))。 ?57 例 1： f(n)=3n+2，求 g(n)，使得 f(n)=O(g(n))。 ②時間復雜性 在算法分析中，通常是用漸近運行時間來度量一個算法。觀察函數(shù) n2log2n+10n2+n 中的低階項 10n2和 n ，當 n值越大，10n2+n對函數(shù)值的影響就越小。即當給出合法的輸入時，為了得到輸出，該算法執(zhí)行時所需要的時間和空間，其中時間尤為重要。根據(jù)觀察結論 （ Page 7），每對合并需要的比較次數(shù)，最少為 2，最多為 3。 MERGE(A,i+1,i+s,i+t) s表示被合并序列的長度（即合并前） t表示合并后序列的長度（初值為 1） i表示位移 5 6 9 10 3 4 8 11 1 2 7 3 4 5 6 8 9 10 11 1 2 7 1 2 3 4 5 6 7 8 9 10 11 47 第 4次迭代： t=8＜ n=11成立 s=8,t=16 i值的范圍： 0 i=0時， i+t≤11不成立，出循環(huán)。 ? s為被合并的子序列長度，初始時為 1，每循環(huán)一次乘以 2； ? t為 s的二倍，即二個子序列合并后的長度，可省略 (見下頁 )； ? 當 n不是 t的整數(shù)倍，出內(nèi)層循環(huán)后執(zhí)行第 8步。如果剩余 3個，則將 2個元素（已排序）和另外 1個元素合并成一個 3元素的排序序列。 37 觀察結論 （ Page 7） 執(zhí)行算法 Merge，將個數(shù)分別為 n1和 n2的非空數(shù)組合并成一個為 n= n1+n2的排序數(shù)組。然后更新指針，若 A[s]≤A[t]，則 s加 1，否則 t加 1； ③當 s=q+1，說明子數(shù)組 A[p..q]的全部元素已進入 B，無需再比較，此時把子數(shù)組余下部分 A[t..r]添加到 B中； ④當 t=r+1，說明子數(shù)組 A[q+1..r]的全部元素已進入 B，無需再比較，此時把子數(shù)組余下部分 A[s..q]添加到 B中； ⑤最后將 B[p..r]復制到 A[p..r]。 31 觀察結論 （ Page 9） 執(zhí)行算法 InsertionSort的元素比較次數(shù)在 n1到 n(n1)/2之間。編寫一函數(shù)，作用為：將 x=A[i]插入到子數(shù)組 A[1..i] 中，使得 A[1..i]按升序排列。 22 23 選擇排序法 ㈠ 選擇算法 假定有一個數(shù)組 A[1..n]， A[i..n]是它的一個子數(shù)組， 1≤i＜ n。 二種情況都有： A[mid+1..n] = ?n/2? = ?n/221? ② 第 3次迭代（循環(huán)）前數(shù)組 A中剩余元素 ? ?n/2? /2? = ?n/4? = ?n/22? = ?n/231 ? ③ 第 j次迭代（循環(huán)）前數(shù)組 A中剩余元素 ?n/2j1? ④ 不管找到與否，搜索 x的終止條件是余下元素僅僅為 1個，即 ?n/2j1? =1 n=10,mid= ?(10+1)/2? =5,剩余元素 A[6..10]，共計 5個 ( ?10/2? )。首先將 x與 A的中間元素比較，A[?(1+14)/2?]=A[7]=10，由于 xA[7]，可以把 A[1..7]掉棄。 ㈢二分搜索 令 A[low..high]為元素按升序排列的非空數(shù)組，數(shù) A[mid] 為中間元素。最重要的是 時間和空間 （即存儲器）資源。指令正確地描述了要完成的任務和它們所執(zhí)行的順序。 問題的可判定性和可解性的研究領域，稱為“可計算理論”。 ① 無論是解題思路還是編寫程序，都是在實施某種算法。沒有輸出的算法毫無意義； – 可行性 ：算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成。計算機程序要對問題的每個對象和處理規(guī)則給出正確詳盡的描述，其中程序的 數(shù)據(jù)結構 和 變量 用來描述問題的對象， 程序結構 ， 函數(shù) 和 語句 用來描述問題的算法、 算法 和 數(shù)據(jù)結構是程序的兩個重要方面。一個算法的復雜性的高低體現(xiàn)在運行該算法所需要的計算機資源的多少。按照該方法，或者掃到 A的第 i個分量時發(fā)現(xiàn)滿足 A[j]=x，或者掃到 A的最后一個分量，經(jīng)檢測仍不滿足 A[j]=x 12 算法復雜性 13 出循環(huán)分析： ① x=A[j]，此時 jn； ② j等于 n，但 A[n]與 x尚未比較（或相等或不相等）。 15 算法 BinarySearch（ Page 4） 輸入： n個元素的數(shù)組 A[1..n]（按升序排列）和元素 x。為了計算最大比較次數(shù)，不失一般性，可假定 x≥A[high] 。由于決策樹的高度為 ?Log2n? ，所以二分搜索法的最大比較次數(shù)為 ?Log2n? +1。 觀察結論 (Page 8) 執(zhí)行算法 SelectionSort所需的元素比較次數(shù)為 n(n1)/2，元素的賦值次數(shù)界于 0與 3(n1)之間。 ①當元素已按升序排列時，元素比較次數(shù)最小，僅為 n1，每個元素 A[i]（ 2≤i≤n）只和 A[i1]比較。然后 i增 1，排序過程直至 i=n結束。 另一方面，比較次數(shù)最多為 n1= n1+n21次。若剩余 1個元素，則讓它進入下一輪合并。 jn22 4 5 9 1 4 6 7 1 2 4 4 5 6 7 9 2 4 5 9 1 4 7 1 2 4 4 5 7 9 ④ 總的迭代次數(shù) k的值范圍為： 2k1＜ n≤ 2k 。 出循環(huán)后， i+s=8+2＜ n=11成立，執(zhí)行 MERGE(A,9,10,n)，最后一個序列長度為 3。 ①在第 1次迭代中，共執(zhí)行了 n/2 次比較。 12?jnjn250 最多比較次數(shù) ( k=log2n) ))211(( kkn ???)211( knnk ???knnnk2???1l o g 2 ??? nnn? ? ?????????? ??? kjjkjjjnnn11 2122????kjjnkn1 2151 觀察結論 （ Page 11) 用算法 BottomUpSort對 n個元素進行排序，當 n為 2的整數(shù)冪時，比較次數(shù)在(nlog2n)/2 到 nlog2nn+1 之間。 ③算法應獨立于機器，無論科技如何進步，對算法運行時間的評估始終成立。因為當很大時低階項便顯得不太重要。如果存在一個自然數(shù) n0和一個正常數(shù) c，使得 n≥n0 ， f(n)≤cg(n) 則稱 f(n)=O(g(n))， n0稱為閾值 。 60 ㈢ Ω符號（讀作 omiga） 定義 （ Page 16） 令 f(n)和 g(n)是從自然數(shù)集到非負實數(shù)集的二個函數(shù)。無論何時，當排序元素個數(shù)不小于某一個閾值 n0時，運行時間至少是 。 f(n)=Θ(g(n))是一個等價關系，由這個關系導出一個等價類，稱為復雜性類。 f(n)=o(g(n))，當且僅當 f(n)=O(g(n)，但 g(n) ≠O(f(n))。換句話說，僅僅是算法需要的工作空間。一般來說，給算法分配的空間越大，算法運行速度就越快，反之亦然。 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) 輸入