2.2-1用Θ記號表示函數(shù)n³/1000-100n²-100n+3

---

舍棄它的低階項，并忽略前面的常數(shù)因子
Θ(n³)

2.2-2考慮排序存儲在數(shù)組A中的n個數(shù)：首先找出A中的最小元素并將其與A[1]中的元素進行交換。接著，找出A中的次最小元素并將其與A[2]中的元素進行交換。對A中前n - 1個元素按該方式繼續(xù)。該算法稱為選擇算法，寫出其偽代碼。該算法維持的循環(huán)不變式是什么？為什么它只需要對前n-1個元素運行？用Θ記號給出選擇排序的最好情況和最壞情況運行時間。

---

（1）偽代碼：
SELECTION-SORT(A)

for i=1 to A.length-1min_loc=ifor j=i+1 to A.lengthif A[j]<A[min_loc]min_loc=jif min_loc!=iswap(A[i],A[min_loc])

附贈C語言實現(xiàn)：

//用C語言實現(xiàn)選擇排序 #include <stdio.h> #define SWAP(X,Y) X=X+Y;Y=X-Y;X=X-Yvoid selectSort(int* a, int n) {int min_loc;int i, j;for (i = 0; i < n-1; i++) {min_loc = i;for (j = i + 1; j < n; j++) {if (a[j] < a[min_loc]) {min_loc = j;//子序列最小值所在位置} }if (min_loc != i) {SWAP(a[min_loc], a[i]);}} }main(){//測試int a[] = { 5,2,4,7,1,3,2,6 };selectSort(a, 8);for (int i = 0; i < 8; i++)printf("%d ", a[i]);//輸出：1 2 2 3 4 5 6 7 }

（2）循環(huán)不變式：在（變量為i的）for循環(huán)每次迭代開始時，子序列A[1…i]包含已排序好的最小的i個元素。
（3）因為在n-1次（變量為i的）循環(huán)后，子序列A[1…n-1]包含A中已排好序的前n-1個最小元素，因此這時A[n]一定已經(jīng)是最大的了。
（4）Θ(n²)

2.2-3再次考慮2.1-3中的線性查找問題。假定要查找的元素等可能地為數(shù)組中的任意元素，平均需要檢查輸入序列的多少元素？最壞情況又如何呢？用Θ記號給出線性查找的平均情況和最壞情況運行時間。

2.1-3的線性查找見上一篇：《算法導(dǎo)論》2.1練習(xí)解答

---

平均要檢查n/2個，Θ(n)
最壞情況要檢查n個，Θ(n)

2.2-4應(yīng)如何修改任何一個算法，才能使之具有良好的最好情況運行時間。

---

可以針對特定條件的問題做針對性的樣例，如果遇到這種（可能是出現(xiàn)概率較高的）特定條件直接輸出準備好的結(jié)果，這是針對特定問題的優(yōu)化。

下一節(jié)：算法導(dǎo)論2.3練習(xí)答案

總結(jié)

以上是生活随笔為你收集整理的《算法导论》2.2练习答案的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。