【正文】 算法復雜性 時間復雜性 空間復雜性 排序 選擇排序 插入排序 自底向上合并排序 冒泡排序 希爾排序 快速排序 3 引言 計算機科學就是 算法研究 4 算法（ Algorithm） 解題方案的準確完整的描述，是在有限步驟內求解某一問題所使用的一組定義明確的規(guī)則。人們的注意力是放在問題的可解和不可解的分類上。一個算法由有限條可完成或機械地執(zhí)行的，有結果指令組成。 ? 計算機的資源。 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 14 ㈡ 順序搜索法分析 最少比較次數為 1，最多比較次數為 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 16 1 4 5 7 8 9 10 12 15 22 23 27 32 35 A[1..14] = A[8..14] = 12 15 22 A[8..10] = ① 要搜索元素 x=22。 若 n是奇數， A[mid+1..n]共有 (n1)/2個元素。 ? 因此，解決同一個問題，算法不同，計算的工作量也不同，所需的計算時間隨之不同，即算法的時間復雜性不同。 A[1..i1]已按升序排列。如下所示： 21)n( n1)(n...21 ????? 因為每個元素 A[i] (2≤i≤n)都和子序列 A[1..i1]中的每個元素比較，這一結果與算法 SelectionSort相一致。 ①使用二個指針 s和 t，初始化時 s=p、 t=q+1， s和 t各自指向 A[p]和 A[q+1]，空數組 B[p..r]用作暫存器； ②每一次比較元素 A[s]和 A[t]，將小的元素添加到 B中。所以，算法 Merge的最少比較次數是n1，最大比較次數為 n1。若剩余 1或 2個，則讓它進入下一輪合并。 42 算法 BottomUpSort（ Page 10） 輸入： n個元素的數組 A[1..n] 輸出：按升序排列的數組 A[1..n] 1. t←1 2. while tn 3. s←t : t←2s : i←0 //i表示要處理數據的起始地址 (簡稱位移 ) 4. while i+t≤n 5. Merge(A,i+1,i+s,i+t) //Merge(A,p,q,r) 6. i←i+t //i表示要處理數據的起始地址 (簡稱位移 ) 7. end while 8. if i+sn then Merge(A,i+1,i+s,n) 9. end while //起始地址 +被合并前子序列長度＜ n，則合并。 出循環(huán)后， i+s=8+4＜ n=11不成立，因此不再合并，最后一個序列長度為 3。 ②在第 2次迭代中， n/2個段（段長 =2）元素序列被合并成 n/4個段（段長 =4），段內有序。 52 時間復雜性 在計算復雜性領域中，主要是研究一個算法所需要的時間和空間。 例某一算法運行時間為 2n3 ，當 n變得很大時，常數 2將不起作用。 55 ① 漸近運行時間 去除表示算法運行時間函數的低價項和首項系數（常數）。 正常數，可以是 0。 ))(()(0)( )(lim ngnfng nfn ????? 蘊含著因此若 若極限是一個正常數，說明函數 f(n)的增長速度和函數 g(n)相差整數倍，基本為同一級別；若極限為 ∞，說明隨著 n的增大，函數f(n)增長的速度要比 g(n)快得多。 ?Ω 符號定義的一個重要推論： f(n)= Ω(g(n))，當且僅當 g(n)=O(f(n)) 63 ㈣ Θ符號（讀作 theta） 定義 （ Page 16） 令 f(n)和 g(n)是從自然數集到非負實數集的二個函數。 表示這二個函數屬同一復雜性類。 ?67 68 我們用 f(n)﹤ g(n)來表示 f(n)是 o(g(n))的。 例 1：在算法 LinearSearch中，僅需要一個內存單元保存搜索結果。但是，減小空間會導致算法速度的降低是毫無疑問的。 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個元素的數組 A[1..n]（按升序排列）和元素 x。同理算法 BinarySearch、 SelectionSort和InsertionSort。 1﹤ log n﹤ n1/2﹤ n﹤ n log n﹤ n2﹤ n3﹤ 2n﹤ n! ?Ｏ 類似于 ≤ ?Ω 類似于 ≥ ?Θ 類似于 ＝ ? o 類似于 ＜ 不要將確切的關系和漸近符號相混淆。 f(n)=o(g(n))，當且僅當 f(n)=O(g(n))，但 g(n)≠O(f(n))。 ))(()(0)( )(l i m ngnfg nfn ?????? 蘊含著因此若Θ符號定義的一個重要推論： f(n)= Θ(g(n)) 當且僅當 f(n)=O(g(n))并且 g(n)=O(f(n)) 極限是一個正常數，說明函數 f(n)的增長速度和函數g(n)的增長速度相差整數倍，基本為同一級別。 解： 當 n0， f(n)=3n+2≥3n。 解 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))。漸近運行時間通常稱為時間復雜性。 54 為了簡化對算法過程的分析，常常會忽略算法中每條語句的真實代價，而用常量 ci表示。 執(zhí)行算法 BottomUpSort的最大比較次數 nlog2nn+1 執(zhí)行算法 SelectionSort的最大比較次數 n(n1)/2 假設一次比較所需的時間為 106秒，當數據個數 n分別為 27 =128 和 220 =1048576時，二個算法執(zhí)行所耗費的時間上限如下表所示： n SelectionSort BottomUpSort 27 106*128(1281)/2 ≈ 106*(128*7128+1) ≈ 220 106* 220 *(2201)/2≈ 106*(220*20 220+1) ≈ 20秒 53 ㈠ 概述 稱“一個算法 A對于輸入 x要用 y秒來運行”是沒有意義的，也是沒有必要的。 ③在第 3次迭代中， n/4個段（段長 =4）元素序列被合并成 n/8個段（段長 =8），段內有序。 出循環(huán)后， i+s=0+8＜ n=11成立，執(zhí)行 MERGE(A,1,8,n)。如果剩余元素數目大于 s，就要將最后一個長度為 s的子序列和剩余元素進行一次合并排序，此時二個子序列合并后的長度小于 t=2s。 4n22n2 4 5 9 4 9 2 5 1 7 4 6 1 4 6 7 2 4 5 9 4 9 2 5 1 7 4 1 4 7 41 剩余元素為 7個 ③ 第 j次迭代（假設 j=3） 生成元素個數為 2j個的排序序列，該序列共有 個。設n1≤n2 ，元素的比較次數在 n1和 n1之間。 34 過程 Merge(A[1..m],p,q,r)（ Page 67） 輸入：數組 A[1..m]和它的三個索引 p,q,r（ 1≤p≤q＜ r≤m），二個子數組 A[p..q]和 A[q+1..r]各自按升序排列。 元素賦值次數等于元素比較次數加上 n1，即 2(n1)至 n(n1)/2+(n1)之間。 依次掃描序號從 j=i1到 j=1的元素，將 x和 A[j]比較。編寫一函數，作用為：從 A[i..n] 中選擇一個最小的數 A[k]（ i＜ k≤n） ，將 A[i]和 A[k]互換（若 k＝ i，無需交換）。 n=11,mid= ?(11+1)/2? =6,剩余元素 A[7..11]，共計 5個 ( ?11/2? )。 ② 在剩余元素 A[8..14]中搜索 x=22， A[?(8+14)/2?]=A[11]=23，由于 xA[11]，可以把 A[11..14]掉棄。假定 xA[mid]，如果 x在A中，則它必定是 A[mid+1]， A[mid+2]， … ， A[high] 中的一個，接下來只需在 A[mid+1..high]中搜索 x。因而算法的復雜性有時間復雜性和空間復雜性之分。計算機按算法指令所描述的順序使得算法的指令能在有限的步驟內終止，或終止于給出問題的解，或終止于指出問題對此輸入數據無解。 數字計算機出現以后，由于有限的資源，提出了盡可能少用資源的有效算法的需求，導致出現計算復雜性的新領域。前者是推理實現，后者是操作實現； ② 算法不是程序，但算法是用程序或偽代碼來描述的。 算法特征 ? 一個算法應具有以下五個重要的特征： –