【正文】 雜性簡單得多，可將時間復雜性的定義和符號移植到空間復雜性的表示。 輸出：如果 x=A[j]， 1≤j≤n，則輸出 j，否則輸出 0。例如： 100n≥n 100n=O(n) n≤100n 100n=Ω(n) n≠100n 100n=Θ(n) 一般地，設 f(n)=aknk+ak1nk1+…+a 1n+a0，則 f(n)=Θ(nk)，它蘊含著 f(n)=O(nk)， f(n)=Ω(nk) 。 ?64 例： f(n)=3n+2，求 g(n)，使得 f(n) =Θ(g(n))。 解 1： 當 n≥2，有 f(n)≤10n2+4n+n=10n2+5n 當 n≥5，有 f(n)≤10n2+5n≤10n2+n2 =11n2 令 g(n)=n2，因為當 n≥5時有 f(n)≤11g(n) 所以 f(n)=O(g(n))=O(n2) 解 2：令 g(n)=n2 )()(2410lim102410lim)()(lim22222nOnfnnnnnnngnfnnn?????????????????同理可證： f(n)=O(nk)， k≥2 59 例 3： f(n)=6*2n+n2，求 g(n)，使得 f(n)=O(g(n))。 在進一步的簡化抽象中，即對運行時間的增長率簡化。根據(jù)觀察結(jié)論 （ Page 7），每對合并需要的比較次數(shù)，最少是 4，最多7。 43 6 10 9 5 3 11 4 8 1 2 7 6 10 5 9 3 11 4 8 1 2 7 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 ㈢ 示例 當 n不是 2的整數(shù)冪時，自底向上合并排序的過程如下所示： 44 第 1次迭代： t=1＜ n=11成立 s=1,t=2 i值的范圍： 0,2,4,8,10 i=0 MERGE(A,1,1,2) i=2 MERGE(A,3,3,4) i=4 MERGE(A,5,5,6) i=6 MERGE(A,7,7,8) i=8 MERGE(A,9,9,10) i=10時， i+t=12≤11不成立，出循環(huán)。特例，如果二個數(shù)組大小為 ?n/2?和 ?n/2? ，需要比較的最大次數(shù)在 ?n/2?和 n1之間。 32 “選擇排序法”和“插入排序法”小結(jié) (1)選擇排序法（往后選擇） Seletion(i) 從 A[i..n]中選擇一個最小的數(shù)（ 1≤i≤n1），將其和 A[i]交換，顯然 A[i]≥A[i1]（當 i≥2時），故 A[1..i]有序。 過程 Selection（參見 Page 8） 輸入： A[i..n] 輸出： A[i..n]，其中 A[i]為 A[i..n]中的最小的數(shù)。 12 15 22 23 27 32 35 考慮搜索數(shù)組 1 7 14 8 11 14 8 9 10 17 A[10] = 22 ③ 在剩余元素 A[8..10]中搜索 x=22， A[?(8+10)/2?]=A[9]=15，由于 xA[9]，可以把 A[8..9]掉棄。 10 ? 對于任意給定的問題，設計出復雜性盡可能低的算法是我們在設計算法過程中追求的一個重要目標責任制，另一方面，當給定的問題已經(jīng)有多種算法時，選擇其中之復雜性最低者，是我們在選用算法適應遵循的一個重要準則，因此，算法的復雜性分析對算法的設計或選用有著重要的指導意義和實用價值。 “計算復雜性”是研究可解類問題的效率。 確定一個程序的運行效率，既可使用數(shù)學分析方法，也可使用實驗測試方法，可以在理論和實踐二個方面作出評估。其次是算法所需要的 存儲空間少和執(zhí)行更快 等。類似地，如果 xA[mid]，只需在A[low..mid1]中搜索 x。 序列： 1 4 5 7 8 9 10 12 15 22 23 27 32 35 ?log214?+1=4 21 ?比較次數(shù)是指元素比較次數(shù)，所以在 while語句中的非元素比較次數(shù)，通常不予計入 ； ?確切講，比較次數(shù)是指布爾表達式“ x=A[mid]”的執(zhí)行次數(shù)； ?由于 ifthenelse嵌套使用，實際元素比較最大次數(shù)應為循環(huán)（迭代）次數(shù)的 2倍，即 2( ?Log2n?+1)。 28 過程 Insertion（參見 Page 89） 輸入： A[1..i1]已按升序排列 輸出： A[1..i] 按升序排列 0. procedure Insertion(i) 1. x←A [i] 2. j←i 1 3. while (j0) and (A[j]x) 4. A[j+1]←A[j] 5. j←j 1 6. end while 7. A[j+1]←x 8. end procedure 29 ㈡ 插入排序算法 設 A[1..n]為 n個元素的數(shù)組，插入排序算法描述如下： ①從子數(shù)組 A[1]開始，單個數(shù)可認為有序； ②接下來，將 A[2]插入到 A[1]的前面或后面，使得A[1..2]有序； ③然后，再將 A[3]插入到 A[1..2]中，使得 A[1..3]有序； ④直到 A[n]插入到 A[1..n1]，使得 A[1..n]有序。 1. ment:B[p..r]為輔助數(shù)組 //或 B[1..m] 2. s←p : t←q+1 : k←p //s和 t分別指向數(shù)組 A二個子數(shù)組元素 3. while (s≤q) and (t≤r) //k指向數(shù)組 B當前空白元素位置 4. if A[s]≤A[t] then B[k]←A[s] : s←s+1 5. else B[k]←A[t] : t←t+1 6. end if 7. k←k+1 //指向數(shù)組 B下一個空白位置 8. end while 9. if s=q+1 then B[k..r]←A[t..r] //子數(shù)組 A[p..q]元素已處理完 10. else B[k..r]←A[s..q] //否則 t=r+1,子數(shù)組 A[q+1..r]已處理完。 ?若 1≤r≤ 2j1(j=3,r=14)，則讓它們進入下一次合并（局部已有序）。 1 2 3 4 5 6 7 8 9 10 11 48 ㈣ 自底向上合并排序算法分析 假設數(shù)組元素個數(shù) n為 2的冪（ n=2k=2log n），外部循環(huán)次數(shù)為 k=log2n。理由如下： ①算法分析通常是將解決同一問題的各種算法之間進行相互比較，執(zhí)行時間是相對的，而不是絕對的。 ④表示時間復雜性的常用函數(shù)有： 常數(shù)： 1 運行時間為恒定值，和輸入無關。 解：令 g(n)=n2 )()(02410lim102410lim)()(lim222nnfnnnnnnngnfnnn?????????????????62 ?在常數(shù)因子范圍內(nèi)， O符號提供了運行時間上界，而Ω 符號提供了運行時間下界。如果對于每一個常數(shù) c0，存在一個自然數(shù) n0，使得 n≥n0 ， f(n)cg(n) 則稱 f(n) = o(g(n)) 。同理算法 BottomUpSort。一般來說，給算法分配的空間越大，算法運行速度就越快，反之亦然。 f(n)=o(g(n))，當且僅當 f(n)=O(g(n)，但 g(n) ≠O(f(n))。無論何時，當排序元素個數(shù)不小于某一個閾值 n0時，運行時間至少是 。如果存在一個自然數(shù) n0和一個正常數(shù) c，使得 n≥n0 ， f(n)≤cg(n) 則稱 f(n)=O(g(n))， n0稱為閾值 。 ③算法應獨立于機器，無論科技如何進步，對算法運行時間的評估始終成立。 ①在第 1次迭代中，共執(zhí)行了 n/2 次比較。 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 。 另一方面，比較次數(shù)最多為 n1= n1+n21次。 ①當元素已按升序排列時，元素比較次數(shù)最小，僅為 n1，每個元素 A[i]（ 2≤i≤n）只和 A[i1]比較。由于決策樹的高度為 ?Log2n? ，所以二分搜索法的最大比較次數(shù)為 ?Log2n? +1。 15 算法 BinarySearch（ Page 4） 輸入： n個元素的數(shù)組 A[1..n]（按升序排列）和元素 x。一個算法的復雜性的高低體現(xiàn)在運行該算法所需要的計算機資源的多少。沒有輸出的算法毫無意義； – 可行性 ：算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成。 問題的可判定性和可解性的研究領域，稱為“可計算理論”。最重要的是 時間和空間 （即存儲器）資源。首先將 x與 A的中間元素比較，A[?(1+14)/2?]=A[7]=10，由于 xA[7]，可以把 A[1..7]掉棄。 22 23 選擇排序法 ㈠ 選擇算法 假定有一個數(shù)組 A[1..n]， A[i..n]是它的一個子數(shù)組， 1≤i＜ n。 31 觀察結(jié)論 （ Page 9） 執(zhí)行算法 InsertionSort的元素比較次數(shù)在 n1到 n(n1)/2之間。 37 觀察結(jié)論 （ Page 7） 執(zhí)行算法 Merge，將個數(shù)分別為 n1和 n2的非空數(shù)組合并成一個為 n= n1+n2的排序數(shù)組。 ? s為被合并的子序列長度，初始時為 1，每循環(huán)一次乘以 2； ? t為 s的二倍，即二個子序列合并后的長度，可省略 (見下頁 )； ? 當 n不是 t的整數(shù)倍，出內(nèi)層循環(huán)后執(zhí)行第 8步。根據(jù)觀察結(jié)論 （ Page 7），每對合并需要的比較次數(shù)，最少為 2，最多為 3。觀察函數(shù) n2log2n+10n2+n 中的低階