【正文】 輸出：如果 x=A[j]， 1≤j≤n，則輸出 j，否則輸出 0。 ?迄今為止所討論的大多數(shù)算法中，增加空間并不可能導致算法速度的加快，有可能反而降低。 76 例 2： 在算法 Merge中，需要和輸入大小相同的存儲器 n個，因此空間復雜性為 Θ(n)。 空間復雜性的計算要比時間復雜性簡單得多，可將時間復雜性的定義和符號移植到空間復雜性的表示。例如： 100n≥n 100n=O(n) n≤100n 100n=Ω(n) n≠100n 100n=Θ(n) 一般地，設(shè) f(n)=aknk+ak1nk1+…+a 1n+a0，則 f(n)=Θ(nk)，它蘊含著 f(n)=O(nk)， f(n)=Ω(nk) 。 例如：“ n是 o(n2)的 ”等價于“ n是 O(n2)，但 n2≠O(n)”。 66 定義 （ Page 19） 令 f(n)和 g(n)是從自然數(shù)集到非負實數(shù)集的二個函數(shù)。 例： f(n)=3n+ g(n)=n，顯然有 f(n)=Θ(g(n))。 ?64 例： f(n)=3n+2，求 g(n)，使得 f(n) =Θ(g(n))。 ?稱排序問題的比較次數(shù)為 Ω(nlog n)，是指無法設(shè)計出一個新的基于比較的排序算法，它的時間復雜性小于nlog n。 令 g(n)=n，因為當 n0時有 f(n)≥3g(n) 所以 f(n)=Ω(g(n))=Ω(n) 例 2： f(n)=10n2+4n+2，求 g(n)，使得 f(n)=Ω(g(n))。如果存在一個自然數(shù) n0和一個正常數(shù) c，使得 n≥n0 ， f(n)≥cg(n) 則稱 f(n) =Ω(g(n))， n0稱為閾值 。 解 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))。 ㈡ O符號（讀作大 O） ))(()()( )(l i m ngOnfng nfn ????? 蘊含著因此若 若極限為非 0正常數(shù)，則函數(shù) f(n)和 g(n)增長速度至多相差常數(shù)倍，或稱為同一級別；若極限為 0，說明隨著 n的增大，函數(shù) f(n)的增長要比 g(n)的增長慢得多。 ③算法分析中的漸近符號有： O、 Ω 、 Θ 、 o。 另外，還可以忽略最高次項的常數(shù)系數(shù)，因為在考慮較大規(guī)模輸入下的率相對于增長率來說系數(shù)是次要的。 在進一步的簡化抽象中，即對運行時間的增長率簡化。 ④算法分析不拘泥小規(guī)模數(shù)據(jù)的輸入，主要關(guān)心在大的輸入實例時，算法運行狀況。因為影響一個算法的實際運行時間與諸多因素有關(guān)（例機器性能、語言選擇、編譯程序優(yōu)劣、程序員素質(zhì)等），甚至無需計算出算法運行時間的近似數(shù)。執(zhí)行該算法的元素賦值次數(shù)為 2nlog2n。根據(jù)觀察結(jié)論 （ Page 7），每對合并需要的比較次數(shù)，最少是 4，最多7。 n個元素被劃分為 n/2個段 （段長 =2），段內(nèi)有序。 MERGE(A,i+1,i+s,i+t) s表示被合并序列的長度（即合并前） t表示合并后序列的長度（初值為 1） i表示位移 3 4 5 6 8 9 10 11 1 2 7 1 2 3 4 5 6 7 8 9 10 11 第 5次迭代： t=16＜ n=11不成立，程序終止執(zhí)行。 MERGE(A,i+1,i+s,i+t) s表示被合并序列的長度（即合并前） t表示合并后序列的長度（初值為 1） i表示位移 6 10 5 9 3 11 4 8 1 2 7 5 6 9 10 3 4 8 11 1 2 7 1 2 3 4 5 6 7 8 9 10 11 46 第 3次迭代： t=4＜ n=11成立 s=4,t=8 i值的范圍： 0,8 i=0 MERGE(A,1,4,8) i=8時， i+t≤11不成立，出循環(huán)。 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)。 k1＜ log2n≤k。 可能剩余的元素個數(shù) r，其大小在 1至 2j1之間 (j=3,r=17)。 2n12n9 4 5 2 1 7 4 6 4 9 2 5 1 7 4 6 9 4 5 2 1 7 4 4 9 2 5 1 7 4 40 ② 第 2次迭代 生成個數(shù)為 4（ =22）的排序序列，共有 = 個。特例，如果二個數(shù)組大小為 ?n/2?和 ?n/2? ，需要比較的最大次數(shù)在 ?n/2?和 n1之間。例如要合并下面二個子數(shù)組： 2 3 66 7 11 13 45 57 就需要 7次比較。 輸出：子數(shù)組 A[p..r]按升序排列。 33 合并二個已排序的表 ㈠ 算法描述 假定有一個數(shù)組 A[1..m]， p， q， r是它的三個索引，并有1≤p≤qr≤m，二個子數(shù)組 A[p..q]和 A[q+1..r]各自按升序排列，重新排列 A中元素的位置，使得子數(shù)組 A[p..r]按升序排列。 32 “選擇排序法”和“插入排序法”小結(jié) (1)選擇排序法（往后選擇） Seletion(i) 從 A[i..n]中選擇一個最小的數(shù)（ 1≤i≤n1），將其和 A[i]交換，顯然 A[i]≥A[i1]（當 i≥2時），故 A[1..i]有序。 ②當元素已按降序排列，并且所有元素各不相同，比較次數(shù)為最大。在掃描的每一步，元素都被移到序號更高的一個位置上，這種過程直到以下情況出現(xiàn)時終止： ①找到一個小于等于 x=A[i]的元素 A[j] ② 元素 A[1]已掃描過（顯然 j=0） 此時可將 x插入到 A[j+1] 。 27 插入排序 ㈠ 插入算法 假定有一個數(shù)組 A[1..n]， A[1..i]是它的一個子數(shù)組（ 1＜ i≤n）。 過程 Selection（參見 Page 8） 輸入： A[i..n] 輸出： A[i..n]，其中 A[i]為 A[i..n]中的最小的數(shù)。 定理 （ Page 6） 對于一個大小為 n的已排序數(shù)組，算法BinarySearch 執(zhí)行比較的最大次數(shù)為 : ?Log2n? +1 ? 容易看出，在最壞的情況下，第一個算法要檢測A的所有 n個分量才能判斷在 A中找不到等于 x的分量； ? 在第二個算法中，最壞的情況下最多只要測 A中的 j+1(j=log2n)個分量，就判斷 x是否在 A中，第一個算法和第二個算法解決的是同一個問題，但在最壞的情況下（所給定的 x不在 A中），兩個算法所檢測的分量個數(shù)卻大不相同，前者要 n=2j個，后者只要 j+1個，可見第二個算法比第一個算法高效得多。 19 當 ?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 20 107 5 2311 11 8 159 32 4 7 9 12 2210 27 3514 可將二分搜索法的執(zhí)行描述為決策樹，紅色的結(jié)點是與 x=22相比較的數(shù)字。 ①第 2次迭代（循環(huán)）前數(shù)組 A中剩余元素 若 n是偶數(shù)， A[mid+1..n]共有 n/2個元素。 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]掉棄。 輸出：如果 x=A[j]， 1≤j≤n，則輸出 j，否則輸出 0。換句話說， A[low..mid]中的項目在后續(xù)比較中被掉棄了。 算法 LinearSearch（ Page 3） 輸入： n個元素的數(shù)組 A[1..n]和元素 x 輸出：如果 x=A[j]（ 1≤j≤n），則輸出 j，否則輸出 0。 10 ? 對于任意給定的問題，設(shè)計出復雜性盡可能低的算法是我們在設(shè)計算法過程中追求的一個重要目標責任制，另一方面，當給定的問題已經(jīng)有多種算法時，選擇其中之復雜性最低者，是我們在選用算法適應遵循的一個重要準則，因此，算法的復雜性分析對算法的設(shè)計或選用有著重要的指導意義和實用價值。所需的資源越多，該算法的復雜性越高；反之，所需的資源越低，該算法的復雜性越低。 ? 通常求解