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