第一章 ? 轉(zhuǎn)自http://www.cnblogs.com/batteryhp/p/4654860.html

思考題

1-1（運(yùn)行時(shí)間的比較）確定時(shí)間t內(nèi)求解的問題的最大規(guī)模。

上面是網(wǎng)上提供的答案。

注意點(diǎn)：

1、最左邊一列的是關(guān)于n的增長(zhǎng)情況描述，值得記住的是這些增長(zhǎng)的排列順序，這是非常有用的，啊，數(shù)分學(xué)好了會(huì)很容易；

2、注意1s內(nèi)能處理的以n為增長(zhǎng)量級(jí)的規(guī)模是10的6次方，記住這個(gè)結(jié)果可以推導(dǎo)出其他增長(zhǎng)量級(jí)的處理規(guī)模；

3、注意這里的lg指的是以2為底的對(duì)數(shù)函數(shù)。

順便做了一張lgn的增長(zhǎng)圖，感受一下：

本來想把n和nlgn畫在一起，可是效果不滿意啊，如下圖：

看得出，nlgn比n增長(zhǎng)的快不少啊！（貌似）

第二章

2.1

2、重寫INSERTION-SORT使之按照升序排列。

其實(shí),只要將while步中的>改成<即可。

//INSERTION-SORT for j = 2 to A.lengthkey = A[j]i = j - 1while i > 0 and A[i] < keyA[i+1] = A[i]i = i - 1A[i+1] = key

3、查找問題，在數(shù)組中查找一個(gè)數(shù)，線性查找，寫偽代碼，并證明循環(huán)不變式。

//find some value for i = 1 to A.lengthif v == A[i]return ielse return NIL

4、兩個(gè)二進(jìn)制數(shù)存儲(chǔ)在兩個(gè)數(shù)組中，將這兩個(gè)數(shù)加和，并將和存儲(chǔ)到另一個(gè)數(shù)組中，寫出形式化描述并且寫出偽代碼。

寫出代碼(親測(cè)有效)：

#include <iostream>using namespace std; const int Num = 10;int main() {int a[Num] = {1,0,1,1,0,1,1,0,1,1};int b[Num] = {0,1,1,1,0,1,0,1,1,1};int c[Num + 1] = {0};int flag = 0;int i;for(i = Num-1;i >= 0;i--){c[i+1] = a[i] + b[i] + flag;if(c[i+1] > 1){c[i+1] = c[i+1]%2;flag = 1;}elseflag = 0;}c[0] = flag;for(i = 0;i <= Num;i++)cout << c[i];cout << endl;return 0; }

?

2.2

1、theta(n^3)

2、排序一個(gè)n個(gè)數(shù)的數(shù)組，規(guī)則是這樣的，將最小的跟第一個(gè)交換，余下最小的的跟第二個(gè)交換…一直做下去，一直到n-1，這個(gè)算法叫做選擇算法，要求寫出循環(huán)不變式和偽代碼，寫出最好最壞運(yùn)行時(shí)間的量級(jí)。

//選擇算法偽代碼 for i = 1 to n - 1min = A[i]for j = i + 1 to nif A[j] < minmin = A[j]exchange A[i] and min

下面是答案上的一種寫法，道理是一樣的：

?

另外，最好和最壞時(shí)間要寫一下。最好無非是已經(jīng)排好了，這時(shí)候也沒用啊，也要尋找最小值……所以，最好最壞都是n^2.

3、考慮2.1-3的線性查找問題，假定要查找的元素等可能地為數(shù)組中的任意元素，平均需要檢查輸入序列的多少元素？最壞情況又如何？

解：直觀想法，平均的話就是半數(shù)的元素?cái)?shù)量；最壞就是全部。可以這么想，現(xiàn)在要從中選一個(gè)元素，每個(gè)元素出現(xiàn)的概率是1/n，需要檢查的個(gè)數(shù)分別為1個(gè)，2個(gè)...n個(gè)，那么取期望，就是（1+2+3...+n）/n 為(n+1)/2個(gè)元素；最壞情況就是n個(gè)，沒什么好說的。換句話說，都是theta(n)的復(fù)雜度。

按照答案上的說法，由于一般時(shí)間在前一半數(shù)組中尋找，一半時(shí)間在后一半數(shù)組中尋找，那么那么平均下來就是中間那個(gè)值嘍~~

4、我們可以如何修改（幾乎所有的）算法可是使之有最好的運(yùn)行時(shí)間？

解：想法：就是最好的輸入唄。。。看一下答案：One can modify an algorithm to have a best-case running time by specializing it to handle a bestcase input efciently.哦。。。

2.3

2、重寫MERGE，當(dāng)L或者R為空時(shí)，把另一組的數(shù)據(jù)全部復(fù)制到A中。

//MERGE 偽代碼 n1 = q - p + 1 n2 = r - q Let L[1..n1] and R[1..n2] be new arrays //由于不需要“哨兵牌”，無需多出一個(gè)元素 for i = 1 to n1L[i] = A[p + i -1] for j = 1 to n2R[j] = A[q + j]i = 1 j = 1for k = p to rif i > n1 //在這里加兩個(gè)判斷while j <= n2A[k] = R[j]k = k + 1 //不要忘了將k和j遞增，這里的k和j得分開遞增j = j + 1breakif j > n2while i <= n1A[k] = L[i]k = k + 1i = i + 1breakif(i < n1 and j < n2) //注意這里的條件判斷，不能直接將二級(jí)的if else 拿上來，否則混亂 if L[i] <= R[j]A[k] = L[i]i = i + 1else A[k] = R[j]j = j + 1 //沒有“哨兵牌”的代碼 #include <iostream> #include <time.h>void MERGESORT(int*, int,int); void MERGE(int*,int,int,int);using namespace std;int main() {clock_t start, end;start = clock();int i;int* arr = new int[100];for (i = 0; i < 100; i++){arr[i] = 100 - i;}MERGESORT(arr,0,99);for (i = 0; i < 100; i++){cout << arr[i] << " ";if (i % 10 == 9){cout << "\n";}}delete[]arr;cout << "__________________" << endl;end = clock();cout << "Run time: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;return 0; } void MERGESORT(int* a, int p, int r) {int q;if (p < r){q = (p + r) / 2;MERGESORT(a, p, q);MERGESORT(a, q + 1, r);MERGE(a, p, q, r);} }void MERGE(int* arr, int p, int q, int r) {int n1 = q - p + 1;int n2 = r - q;int* Left = new int[n1];int* Right = new int[n2];int i, j;for (i = 0; i < n1; i++)Left[i] = arr[p + i];for (j = 0; j < n2; j++)Right[j] = arr[q + j + 1];i = 0;j = 0;for (int k = p; k <= r; k++){if (i >= n1){while (j < n2){ arr[k] = Right[j];k++;j++;}break;}if (j >= n2){while (i < n1){ arr[k] = Left[i];k++;i++;}break;}if (i < n1 && j < n2){if (Left[i] <= Right[j]){arr[k] = Left[i];i++;}else{arr[k] = Right[j];j++;}}}delete []Left;delete []Right;}

3、利用數(shù)學(xué)歸納法證明下面的式子成立，其中T(n)=nlgn:

證明:

(1)基本情況，n = 2時(shí)，T(n)=2lg2=2成立；

(2)假設(shè)當(dāng)n = 2^k 時(shí)成立，即T(2^k) = (2^k)lg(2^k),下面證明當(dāng) n = 2^(k + 1)時(shí)成立。T(2^(k+1)) = 2T(2^k)+2^(k+1)=2((2^k)lg(2^k))+2^(k+1)=2^(k+1)(lg(2^k)+1)=2^(k+1)(lg(2^k)+lg2)=2^(k+1)(lg(2^k * 2))=2^(k+1)(lg(2^(k+1))),n=2^(k+1)時(shí)也成立。

4、我們可以把插入排序表示為以下一個(gè)遞歸過程。為了排序A[1..n],遞歸地排序A[1..n-1]，然后把A[n]插入到已經(jīng)排序的數(shù)組A[1..n-1]中。為插入排序的這個(gè)遞歸版本的最壞情況寫一個(gè)遞歸式。

解：我們考慮最倒霉的情況，在插入排序中，原數(shù)組是按照倒序排列的，那么每次有一個(gè)新的數(shù)，就得讓它跑到已經(jīng)排好的數(shù)組的最前面……那么新插入一個(gè)元素時(shí)的時(shí)間復(fù)雜度就是theta(n)，因?yàn)榭傄容^n-1次，再加上判斷下標(biāo)不越界，復(fù)雜度就是n了：

5、回顧查找問題，2.1-3，注意到如果A已經(jīng)被排序了，那么新的值v可以先與A的中間元素進(jìn)行比較，那么根據(jù)比較的結(jié)果原數(shù)組中的一半就可以不再考察了。二分查找算法就是不斷重復(fù)這個(gè)過程，每次的序列數(shù)量減半。寫出二分查找的迭代或者遞歸的偽代碼，并且證明最壞運(yùn)行時(shí)間為theta(lgn).

解：需要注意的是，被查找的數(shù)組必須是已經(jīng)排序好的數(shù)組。

//遞歸版本的二分查找 BINARYSEARCH(A,v,p,r) if p >= r and A[p] != vreturn NIL else q = (p + r)/2if A[q] == vreturn qelse if A[q] < vreturn BINARYSORT(A,v,q+1,r)else return BINARYSORT(A,v,p,q-1) //遞歸版本二分查找代碼 #include <iostream> #include <time.h>using namespace std;int Binarysearc(int*, int, int, int);int main() {clock_t start, end;start = clock();int* arr = new int[100];int v = 70;for (int i = 0; i < 100; i++){arr[i] = i;}int position = Binarysort(arr, v, 0, 99);cout << position << endl;delete[]arr;cout << "__________________" << endl;end = clock();cout << "Run time: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;return 0;}int Binarysearch(int* arr, int v, int p, int r) {if (p > r && arr[p] != v)return -1;else{int q = (p + r) / 2;if (arr[q] == v)return q;else if (arr[q] < v)Binarysort(arr, v, q + 1, r);elseBinarysort(arr, v, p, q - 1);}}

關(guān)于迭代版本：

//迭代版本的二分查找 A is a array v is a value p,r are the min and max index of A ITERATIONSEARCH(A,v,p,r)while(p <= r)q = (p + r)/2if A[q] == vreturn qelse ifv < A[q]r = qelsep = qreturn NIL //迭代版本的二分查找 #include <iostream> #include <time.h>using namespace std;int Iterattionsearch(int*, int, int, int);int main() {clock_t start, end;start = clock();int* arr = new int[100];int v = 70;for (int i = 0; i < 100; i++){arr[i] = i;}int position = Iterattionsearch(arr, v, 0, 99);cout << position << endl;delete[]arr;cout << "__________________" << endl;end = clock();cout << "Run time: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;return 0;}int Iterattionsearch(int* arr, int v, int p, int r) {while (p <= r){int q = (p + r) / 2;if (arr[q] == v)return q;else if (arr[q] < v)p = q + 1;elser = q - 1;}}

下面考察其最壞時(shí)間的復(fù)雜度：

元素個(gè)數(shù)為n的數(shù)組，最壞需要除2*lgn次2才會(huì)得到結(jié)果，故最壞時(shí)間復(fù)雜度為theta(lgn).這樣考慮m分查找，其時(shí)間復(fù)雜度為m*lgm(n).lgm是以m為底的對(duì)數(shù)函數(shù)，那么對(duì)于給定的n，m是多少時(shí)時(shí)間最短呢？做了一些實(shí)驗(yàn)，表明m=3的時(shí)候函數(shù)m*lgm(n)最小，或者說時(shí)間復(fù)雜度最低，但是效率據(jù)說不是最高的。有空試一試~

?

6、在插入排序中，對(duì)于已經(jīng)排好序的A[1..n-1]，需要線性掃描這個(gè)已經(jīng)排好的序列。現(xiàn)在要對(duì)插入排序進(jìn)行優(yōu)化，將這個(gè)線性排序的部分改成二分查找的方式，使最壞時(shí)間變?yōu)閠heta(nlgn)(原來是theta(n^2))如何實(shí)現(xiàn)呢？

解：第一想法，不可能吧…畢竟需要一個(gè)一個(gè)往后挪位置啊……

yep，看了看其他人的答案，確實(shí)是這樣的，即使可以使用二分查找找到位置，但是后面移位的過程時(shí)間復(fù)雜度仍然是theta(n),整體的復(fù)雜度還是theta(n^2).

7、請(qǐng)給出一個(gè)復(fù)雜度為theta(nlgn)的算法，給定n個(gè)整數(shù)的集合S和另一個(gè)整數(shù)x，該算法能確定S中是否存在兩個(gè)其和剛好為x的元素。

解：自己的想法：先排序（歸并排序），然后第一個(gè)數(shù)從前面開始找，那么x減去這個(gè)數(shù)的結(jié)果就是需要找的數(shù)，再用二分查找去找這個(gè)數(shù)！總的復(fù)雜度就是theta(nlgn).

yep,看了下答案確實(shí)是這樣。

截圖一下：

思考題

2-1（在并歸排序中對(duì)小數(shù)組采用插入排序）雖然歸并排序的最壞運(yùn)行時(shí)間是theta(nlgn)，而插入排序的最壞運(yùn)行時(shí)間是theta(n^2)，但是插入排序中的常數(shù)因子可能使得在n較小時(shí)運(yùn)行時(shí)間更短。因此在并歸排序中當(dāng)子問題編的足夠小時(shí)，采用插入排序使得遞歸的葉變粗是有意義的。考慮對(duì)歸并排序的修改，其中使用插入排序來排序長(zhǎng)度為k的n/k個(gè)子表，然后使用標(biāo)準(zhǔn)的合并機(jī)制來合并這些子表，這里k是一個(gè)特定的值。

a.證明：插入排序最壞情況可以在theta(nk)時(shí)間內(nèi)排序每個(gè)長(zhǎng)度為k的n/k個(gè)子表。

b.表明在最壞情況下如何在theta(nlg(n/k))時(shí)間內(nèi)合并這些子表。

c.假定修改后的算法的最壞情況運(yùn)行時(shí)間為theta(nk+nlg(n/k))，要使修改后的算法與標(biāo)準(zhǔn)的歸并排序具有相同的運(yùn)行時(shí)間，作為n的一個(gè)函數(shù)，借助theta記號(hào)，k的最大值是什么？

d.在實(shí)踐中，我們應(yīng)該如何選擇k？

解:打完上面的思考題，感覺……跟練習(xí)題不是一個(gè)次元的！臥槽，太有挑戰(zhàn)性。

a.證明：每個(gè)子表的時(shí)間復(fù)雜度為theta(k^2)，共有n/k個(gè)子表，故總時(shí)間為theta(nk).

b.n/k個(gè)列表兩兩合并，合并完繼續(xù)合并，共需要lg(n/k)層，每層時(shí)間復(fù)雜度均為theta(n)，所以合并共需要theta(nlg(n/k))的時(shí)間。

c.標(biāo)準(zhǔn)的歸并排序的時(shí)間復(fù)雜度為theta(nlgn)，需要theta(nlgn)=theta(nk+nlg(n/k))，這時(shí)候k的最大值只能是k=theta(lgn).

d.k的選取標(biāo)準(zhǔn)是長(zhǎng)度為k的子列，插入排序要比歸并排序快。額，這么說好像不負(fù)責(zé)任。。。（這里需要用紙來演算一下）

網(wǎng)上有一個(gè)答案可能靠譜：這是個(gè)實(shí)驗(yàn)問題，應(yīng)該在k的合法范圍內(nèi)測(cè)試可能的k，用T-INSERTION-SORT(k)表示k個(gè)元素的插入排序時(shí)間，T-MERGE-SORT(k)表示k個(gè)元素的合并排序時(shí)間。該問題等價(jià)于測(cè)試求解T-INSERTION-SORT(k)/T-MERGE-SORT(k)比值最小的k值。

下面這段話來自：http://blog.kingsamchen.com/archives/715

由反證法可以得到，k的階取值不能大于Θ(logn)，并且這個(gè)界可以保證插排優(yōu)化的漸進(jìn)時(shí)間不會(huì)慢于原始?xì)w并排序。

由于對(duì)數(shù)函數(shù)的增長(zhǎng)特點(diǎn)，結(jié)合實(shí)際排序規(guī)模，k得實(shí)際取值一般在10~20間。

在歸并中利用插入排序不僅可以減少遞歸次數(shù)，還可以減少內(nèi)存分配次數(shù)（針對(duì)于原始版本）。

?

ps.需要對(duì)比驗(yàn)證一下。

2-2（冒泡排序的正確性）冒泡排序是一種流行但低效的排序算法，它的作用是反復(fù)交換相鄰的未按次序排列的元素。

//冒泡排序偽代碼 BUBBLESORT(A) for i = 1 to A.length -1 for j = A.length downto i + 1if A[j] < A[j - 1]exchange A[j] with A[j - 1]

a.假設(shè)A’是BUBBLESORT(A)的輸出。為了證明BUBBLESORT正確，我們必須 證明它將終止并且有：

A'[1] <= A'[2]...<= A'[n] (2.3)

其中n=A.length.為了證明BUBBLESORT確實(shí)完成了排序，我們還需要證明什么？下面兩部分將證明不等式(2.3)。

b.為第二層的for循環(huán)精確地說明一個(gè)循環(huán)不變式，并證明該循環(huán)不變式成立。你的證明應(yīng)該使用本章中給出的循環(huán)不變式的結(jié)構(gòu)。

c.使用(b)部分證明的循環(huán)不變式的終止條件，為第一層說明一個(gè)循環(huán)不變式，這個(gè)不變式就能證明式子(2.3)。證明中應(yīng)該使用本章中給出的循環(huán)不變式證明的結(jié)構(gòu)。

d.冒泡排序的最壞情況運(yùn)行時(shí)間是多少？與插入排序的運(yùn)行時(shí)間相比，性能如何？

解：

b.第二層循環(huán)使得將未排序的數(shù)組中最小的一個(gè)移動(dòng)到最前面。

初始：j=n，子數(shù)組為A[j-1..n]=A[n-1..n]有兩個(gè)元素。在循環(huán)內(nèi)部，通過條件交換語句，可以保證A[n-1] < A[n]成立。因此A[j-1]是A[j-1..n]中的最小元素。 保持：每次迭代開始時(shí)，A[j]是A[j..n]中的最小元素。在迭代操作中，當(dāng)A[j] < A[j-1]時(shí)交換，因此總有A[j-1] < A[j]。可知，本次迭代操作完成后，A[j-1]一定是A[j-1..n]中的最小元素。 終止：j=i+1時(shí)退出，因此結(jié)束時(shí)，A[i]一定是A[i..n]中的最小元素。http://blog.csdn.net/cppgp/article/details/7161701

c.第一層循環(huán)使得不斷增加已經(jīng)排序好的數(shù)組元素，知道全部排好。

初始：i=1，是A中的第一個(gè)元素，因此內(nèi)部循環(huán)完成后，可以保證A[1]中保存A[1..n]的最小元素。 保持：每次遞增i時(shí)，執(zhí)行內(nèi)部循環(huán)，因此A[i]中保存A[i..n]中的最小元素。可知每次內(nèi)部循環(huán)完成后，都有 A[1] ≤ A[2] ≤ ... ≤ A[i] 終止：i=length[A]時(shí)終止，此時(shí)有 A[1] ≤ A[2] ≤ ... ≤ A[n]。轉(zhuǎn)自：http://blog.csdn.net/cppgp/article/details/7161701

d.兩個(gè)的最壞運(yùn)行時(shí)間都是theta(n^2)，但是在插入排序中，最好的時(shí)間可以達(dá)到theta(n),冒泡排序一直是theta(n^2).

2-3(霍納(Horner)規(guī)則的正確性)給定系數(shù)a0,a1,a2,…,an和x的值，代碼片段

y = 0 for i = n downto 0y = ai + xy

實(shí)現(xiàn)了用于求值多項(xiàng)式

的霍納規(guī)則.

ps.在中國(guó)，這個(gè)算法叫做秦九韶算法。

a.借助theta符號(hào)，實(shí)現(xiàn)霍納規(guī)則的以上代碼片段的運(yùn)行時(shí)間是多少？

b.編寫偽代碼來實(shí)現(xiàn)樸素的多項(xiàng)式求值算法，該算法從頭開始計(jì)算多項(xiàng)式的每項(xiàng)。該算法的運(yùn)行時(shí)間是多少？與霍納規(guī)則相比，其性能如何？

c.考慮以下循環(huán)不變式：

在第2-3行for循環(huán)每次迭代的開始有

把沒有項(xiàng)的和式解釋為等于0.遵照本章中的循環(huán)不變式證明的結(jié)構(gòu)，使用該循環(huán)不變式來證明終止時(shí)有

d.最后證明上面給出的代碼片段將正確地求由系數(shù)a0,a1,a2,a3…,an刻畫的多項(xiàng)式。

解：啊啊啊，多項(xiàng)式求值的問題，原來換一種寫法就是一種新規(guī)則，霍納規(guī)則。

a.這應(yīng)該是theta(n）吧……很顯然的；n次多項(xiàng)式用到n次加法，n次乘法。

b.偽代碼如下：

//多項(xiàng)式一般求解偽代碼 y = 0 for i = 1 to nbase = 1for j = 1 to i base = base*xy = y + ai*base y = y + a0 return y

上述偽代碼的復(fù)雜度是theta(n^2)（1+2+3+…+n），顯然霍納規(guī)則比一般算法好得多，霍納算法是theta(n)啊，那么問題來了：霍納算法節(jié)省了哪一部分的運(yùn)算呢？還能不能更簡(jiǎn)化呢？

自己想一想，一般的算法重復(fù)計(jì)算了好多次x的乘方，每一次乘方都需要重新計(jì)算，而霍納算法通過改變計(jì)算順序，成功避免了這一問題（trick在哪里？還沒想明白）。我想到一個(gè)辦法，一般算法的每次結(jié)果存起來再用！這樣的復(fù)雜度也是theta(n),不過這也有存儲(chǔ)的問題，偽代碼：

//多項(xiàng)式改進(jìn)偽代碼 y = 0 arr[n+1] arr[0] = 1 for i = 1 to n arr[i] = a[i-1]*xy = y + ai * arr[i] y = y + a0 return y

c.題目的敘述是對(duì)的，進(jìn)行了驗(yàn)證，除了第一步遇到-1次項(xiàng)外，感覺比較巧妙，利用循環(huán)不變式可以證明。

初始：i=n，y[n] = 0，迭代開始時(shí)，循環(huán)后有y[n] = a[n]。 保持：對(duì)于任意 0 ≤ i ≤ n，循環(huán)后有：y[i] = a[i] + y[i+1] * x = a[i] + (a[i+1] * x + a[i+2] * x + ... + a[n] * x^(n-(i+1))) * x= a[i] + a[i+1] * x + a[i+2] * x^2 + ... + a[n] * x^(n-i) 終止：i小于0時(shí)終止，此時(shí)有 y[0] = a[0] + a[1] * x + a[2] * x^2 + a[n] * x^n證明和y = Σ a[k+i+1] * x^k的關(guān)系：k 從0到n-(i+1)，等價(jià)于 0 ≤ k ≤ n-(i+1)。因此y = Σ a[k+i+1] * x^k= a[i+1] + a[i+2] * x + ... + a[n-(i+1)+i+1] * x^(n-i)= a[i+1] + a[i+2] * x + ... + a[n] * x^(n-i)由于i+1循環(huán)之后和i循環(huán)之前的值相等，用y'[i]表示i循環(huán)之前的值，則有：y'[i] = y[i+1]霍納規(guī)則循環(huán)不變式的結(jié)果表明：y[i] = a[i] + a[i+1] * x + a[i+2] * x^2 + ... + a[n] * x^(n-i)因此有：y'[i] = y[i+1] = a[i+1] + a[i+2] * x + ... + a[n] * x^(n-(i+1))令k=n-(i+1)，則n=k+i+1，所以：y'[i] = a[i+1] + a[i+2] * x + ... + a[k+i+1] * x^(k+i+1-(i+1))= a[i+1] + a[i+2] * x + ... + a[k+i+1] * x^k用y表示y'[i]，則有：y = a[i+1] + a[i+2] * x + ... + a[k+i+1] * x^k= Σ a[k+i+1] * x^k其中 k從0到n-(i+1)證畢。轉(zhuǎn)自：http://blog.csdn.net/cppgp/article/details/7161701

上面的證明很細(xì)致，再次感謝。

d.這一步把循環(huán)不變式寫到0就可以了，c中已經(jīng)證明了，在第二個(gè)證明里。

2-4（逆序?qū)?#xff09;假設(shè)A[1..n]是一個(gè)有n個(gè)不同數(shù)的數(shù)組。若 i < j 且 A[i] > A[j]，則對(duì)偶(i,j)稱為A的一個(gè)逆序?qū)?inversion)。

a.列出數(shù)組<2,3,8,6,1>的5個(gè)逆序?qū)Α?/p>

b.由集合{1,2,…,n}中的元素構(gòu)成的什么數(shù)組具有最多的逆序?qū)?#xff1f;它有多少逆序?qū)?#xff1f;

c.插入排序的運(yùn)行時(shí)間與輸入數(shù)組中逆序?qū)Φ臄?shù)量之間是什么關(guān)系？證明你的回答。

d.給出一個(gè)確定在n個(gè)元素的任何排列中逆序?qū)?shù)量的算法，最壞情況需要theta(nlgn)時(shí)間。（提示：修改歸并排序）

解;

a.說白了就是前面比后面大，那么就有 (1,5),(2,5),(3,4),(3,5),(4,5).

b.啊啊啊，都讓開，讓我來回答這個(gè)題！

哈哈，大家記不記得高等代數(shù)里面在講矩陣按行或者按列展開的時(shí)候，每一項(xiàng)的正負(fù)號(hào)怎么決定的？--對(duì)了，就是-1的這個(gè)元素(所在行+所在列)次方！好像跟這個(gè)題沒什么關(guān)系哈。。。不過下面這個(gè)就很有關(guān)系了：在近世代數(shù)里面，在學(xué)對(duì)換群的時(shí)候接觸過這方面的內(nèi)容，好吧，我忘了是哪一塊內(nèi)容了，待我查查或者問問別人。。

那么這個(gè)題目呢，顯然數(shù)組逆序排的時(shí)候逆序?qū)ψ疃嗬瞺~最多的個(gè)數(shù)呢，就是 從右向左數(shù) 1+2+3…+n-1=n(n-1)/2對(duì)。

c.這個(gè)問題用歸納法想一下，沒有逆序?qū)Φ臅r(shí)候時(shí)間是n，逆序排的時(shí)候是n^2，那么中間呢？啊，是這樣，移動(dòng)的次數(shù)不用考慮，只要考慮比較的次數(shù)就可以了，比較的越多，移動(dòng)的就越多，這個(gè)比較的次數(shù)決定了插入排序的運(yùn)行時(shí)間，而且造成比較的原因就是逆序?qū)α?#xff0c;所以對(duì)于已經(jīng)排好的A[1..n-1]而言，A[n]比A[1..n-1]中小的個(gè)數(shù)就是比較的次數(shù)（其實(shí)應(yīng)該是比較次數(shù)-1），這么說來從第一個(gè)數(shù)開始想，總的逆序?qū)?shù)目就是需要進(jìn)行比較的總數(shù)了。

d.想了半天，由于合并總共lgn層，那么每一層求逆序?qū)Φ膹?fù)雜度就是n，從網(wǎng)上看了幾個(gè)答案，好像沒有幾個(gè)好好寫的，找到了一個(gè)挺好，說一說想法。加入左右兩個(gè)子數(shù)組已經(jīng)排好序，那么只要從右面數(shù)組中選出一個(gè)，那么現(xiàn)在左邊數(shù)組中對(duì)應(yīng)的剩下的那一部分都比剛才從右邊選出的大，那么對(duì)應(yīng)的逆序?qū)投喑鲎筮吺Ｏ略氐臄?shù)量那么多個(gè)。ps.在此問題中，在子序列合并之前，每一個(gè)排好的子序列自身數(shù)組中的逆序?qū)σ呀?jīng)在上一步求出，合并的過程是在求子序列之間的逆序?qū)?shù)量。

inversions = 0 //全局變量 COUNT-INVERSIONS(A,p,r) if p < rq = （p + r）/2COUNT-INVERSIONS(A,p,r) COUNT-INVERSIONS(A,p,r) MERGE-INVERSIONS(A,p,q,r) MERGE-INVERSIONS(A,p,q,r) n1 = q - p + 1 n2 = r - q let L[1 : : n1 + 1] and R[1 .. n2 + 1] be new arrays for i = 1 to n1L[i ] = A[p + i - 1] for j = 1 to n2R[j] = A[q + j] L[n1 + 1] = ∞ R[n2 + 1] = ∞ i = 1 j = 1for k = p to rif L[i] > R[j] A[k] = R[i] inversiongs = inversiongs + n1 – i + 1 i = i + 1else A[k] = R[j] j = j + 1

思想轉(zhuǎn)自：http://www.cnblogs.com/lilith/archive/2012/11/21/2780319.html，自己作了修改。上面的算法還需要程序驗(yàn)證，這是下一步的工作，下一步要把前面提到的偽代碼實(shí)現(xiàn)一遍。這一篇寫的太長(zhǎng)了。

轉(zhuǎn)載于:https://www.cnblogs.com/mhpp/p/7657640.html

總結(jié)

以上是生活随笔為你收集整理的《算法导论》读书笔记--第1、2章课后题 （转）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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