【正文】 ：數(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 83 算法 COUNT1(Page 21) 輸入： n=2k,k為正整數(shù) 輸出：執(zhí)行次數(shù) count 1. count ←0 2. while n≥1 3. for j←1 to n 4. count ← count +1 5. end for 6. n ←n/2 7. end while 8. return count 算法運行時間： ? ?nnP a g ennnkkjjkjj?????????? ??? ????12))(50(212212 0084 算法 COUNT3(Page 2223) 輸入： k為正整數(shù) 輸出：執(zhí)行次數(shù) count 1. count ←0 2. for i←1 to n 3. j← 2 4. while j≤n 5. j← j2 6. count ← count +1 7. end while 7. end for 8. return count 算法運行時間： ? ?nn lo glo g?kn 22?85 算法 PSUM(Page 23) 輸入： k為正整數(shù) 輸出：對于 1和 n之間的每個完全平方數(shù) j，輸出 1. 2. for j←1 to k 3. sum[j]← 0 4. for i←1 to j2 5. j← j2 6. sum[j]← sum[j] + i 7. end for 7. end for 8. return sum[1…k] 算法運行時間： ? ? ? ?126)12)(1( nkkkkjkj?????????2kn???jii1nk ?。同理算法 BottomUpSort。 69 例 （ Page17) f(n)=10n2+20n，求 g(n)，使得 f(n) =Θ(g(n))。如果對于每一個常數(shù) c0，存在一個自然數(shù) n0，使得 n≥n0 ， f(n)cg(n) 則稱 f(n) = o(g(n)) 。 解： 當(dāng) n≥2， f(n)=3n+2≤3n+n=4n 當(dāng) n≥1， f(n)=3n+2≥3n 故當(dāng) n≥2，有 3n≤f(n)≤4n 令 g(n)=n，因為當(dāng) n≥2時有 3g(n)≤f(n)≤4g(n) 所以 f(n)= Θ(n) 解 2：令 g(n)=n )()(323lim323lim)()(limnnfnnnnngnfnnn???????????????65 Θ符號提供了算法運行時間的精確描述，由于算法InsertionSort的運行時間由線性到平方排列，因此不能用 Θ描述。 解：令 g(n)=n2 )()(02410lim102410lim)()(lim222nnfnnnnnnngnfnnn?????????????????62 ?在常數(shù)因子范圍內(nèi)， O符號提供了運行時間上界，而Ω 符號提供了運行時間下界。 解： 當(dāng) n≥4，有 n2≤ 2n 故當(dāng) n≥4，有 f(n) = 6*2n+n2 ≤ 6*2n + 2n = 7*2n 令 g(n)= 2n ，因為當(dāng) n≥4時有 f(n)≤7g(n) 所以 f(n)=O(g(n))=O(2n) ?O符號提供了運行時間的上界； ?算法 InsertionSort執(zhí)行的比較次數(shù)最多為 2（ n(n1)/2 =）， c為某個適當(dāng)選擇的常數(shù)，則稱該算法的運行時間是 O(n2)。 ④表示時間復(fù)雜性的常用函數(shù)有： 常數(shù)： 1 運行時間為恒定值，和輸入無關(guān)。在簡化過程中，僅考慮公式中的最高次項。理由如下： ①算法分析通常是將解決同一問題的各種算法之間進(jìn)行相互比較，執(zhí)行時間是相對的，而不是絕對的。 49 最少比較次數(shù)（ k=log2n） ④ 在第 j次迭代中， 個段（段長 =2j1）元素序列被合并成 個段（段長 =2j），段內(nèi)有序。 1 2 3 4 5 6 7 8 9 10 11 48 ㈣ 自底向上合并排序算法分析 假設(shè)數(shù)組元素個數(shù) n為 2的冪（ n=2k=2log n），外部循環(huán)次數(shù)為 k=log2n。 出循環(huán)后， i+s=10+1=11＜ n=11不成立，因此不再合并，最后一個序列長度為 1（或稱剩下的元素個數(shù)）。 ?若 1≤r≤ 2j1(j=3,r=14)，則讓它們進(jìn)入下一次合并（局部已有序）。 觀察結(jié)論 （ Page 7） 執(zhí)行算法 Merge，將個數(shù)分別為 n1和 n2的非空數(shù)組合并成一個為 n= n1+n2的排序數(shù)組，元素的賦值次數(shù)恰好是 2n。 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當(dāng)前空白元素位置 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]已處理完。然后 i增 1，排序過程直至 i=n1結(jié)束。 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 ㈡ 插入排序算法 設(shè) A[1..n]為 n個元素的數(shù)組，插入排序算法描述如下： ①從子數(shù)組 A[1]開始，單個數(shù)可認(rèn)為有序； ②接下來，將 A[2]插入到 A[1]的前面或后面，使得A[1..2]有序； ③然后，再將 A[3]插入到 A[1..2]中，使得 A[1..3]有序； ④直到 A[n]插入到 A[1..n1]，使得 A[1..n]有序。 0. procedure Selection(i) 1. k←i 2. for j←i+1 to n 3. if A[j]A[k] then k←j 4. end for 5. if k≠i then 交換 A[i]和 A[k] 6. end procedure 24 ㈡ 選擇排序算法 設(shè) A[1..n]為 n個元素的數(shù)組，選擇排序算法如下： ①首先在 n個元素中找到最小元素，將其存放在 A[1]中； ②然后在剩下的 n1個元素中找到最小元素，將其存放在A[2]中； ③重復(fù)上述過程，直至在二個元素 A[n1]和 A[n]中找到較小元素，將其存放在 A[n1]中。 序列： 1 4 5 7 8 9 10 12 15 22 23 27 32 35 ?log214?+1=4 21 ?比較次數(shù)是指元素比較次數(shù)，所以在 while語句中的非元素比較次數(shù)，通常不予計入 ； ?確切講，比較次數(shù)是指布爾表達(dá)式“ x=A[mid]”的執(zhí)行次數(shù)； ?由于 ifthenelse嵌套使用，實際元素比較最大次數(shù)應(yīng)為循環(huán)（迭代）次數(shù)的 2倍，即 2( ?Log2n?+1)。 ④ 留在序列中僅剩一個項目 A[10]=22，最后找到 x=A[10]，搜索成功完畢（若 x≠A[10]，則 low≤high條件不成立，出循環(huán)）。類似地，如果 xA[mid]，只需在A[low..mid1]中搜索 x。 ? 關(guān)于算法的復(fù)雜性，有兩個問題要弄清楚： – 用怎樣的一個量表達(dá)一個算法的復(fù)雜性； – 對于一個對定的一個算法，怎樣具體計算它的復(fù)雜性 11 算法復(fù)雜性 ? 問題：已知不重復(fù)且已經(jīng)按從小到大排好的 n個整數(shù)的數(shù)組 A[1..n]。其次是算法所需要的 存儲空間少和執(zhí)行更快 等。效率是用解決問題所需的時間和空間來描述的。 確定一個程序的運行效率，既可使用數(shù)學(xué)分析方法，也可使用實驗測試方法，可以在理論和實踐二個方面作出評估。 5 算法分析（ Algorithm Analysis） 算法分析研究的目標(biāo)為：算法一旦轉(zhuǎn)換成某種語言的程序，該程序在計算機(jī)上運行，需要多少時間和存儲空間才能完成解題方案。 “計算復(fù)雜性”是研究可解類問題的效率。 ? 通常求解一個問題可能會有多種算法可供選擇，選擇的主要標(biāo)準(zhǔn)首先是算法的 正確性和可靠性，簡單性和易理解性 。 10 ? 對于任意給定的問題，設(shè)計出復(fù)雜性盡可能低的算法是我們在設(shè)計算法過程中追求的一個重要目標(biāo)責(zé)任制，另一方面，當(dāng)給定的問題已經(jīng)有多種算法時，選擇其中之復(fù)雜性最低者，是我們在選用算法適應(yīng)遵循的一個重要準(zhǔn)則，因此，算法的復(fù)雜性分析對算法的