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