算法設(shè)計與分析課后習(xí)題

1、第一章1. 算法分析題算法分析題11 求下列函數(shù)的漸進(jìn)表達(dá)式(1). 3n2 + 10n < 3n2 + 10n2 = 13n2 = O(n2)(2). n2 / 10 + 2n當(dāng)n>5是，n2 < 2 n所以，當(dāng)n >= 1時，n2/10 < 2 n故: n2/10 + 2n < 2 n + 2n = 2*2n = O(2n)(3). 21 + 1/n < 21 + 1 = 22 = O(1)(4). log(n3)=3log(n)=O(log(n)(5). 10log(3n) = (10log3)n = O(n)算法分析題1-6(1) 因?yàn)椋篺(n

2、)=log(n2) = 2log(n); g(n) = log(n) + 5所以：f(n)=(log(n)+5) =(g(n)(2) 因?yàn)椋簂og(n) < n ; f(n) = 2log(n); g(n)= n 所以：f(n) = O(g(n)(3) 因?yàn)椋簂og(n) < n; f(n) = n; g(n) = log(n2) = 2log(n)所以；f(n) = (g(n)(4) 因?yàn)椋篺(n) = nlogn +n; g(n) = logn所以：f(n) =(g(n)(5) 因?yàn)? f(n) = 10; g(n) = log(10)所以:f(n) =(g(n)(6) 因?yàn)?

3、 f(n)=log2(n); g(n) = log(n)所以: f(n) =(g(n)(7) 因?yàn)? f(n) = 2n < 100*2n; g(n)=100n2; 2n > n 2所以: f(n) = (g(n)(8) 因?yàn)椋篺(n) = 2n; g(n) = 3 n; 2 n < 3 n所以: f(n) = O(g(n)習(xí)題19 證明：如果一個算法在平均情況下的計算時間復(fù)雜性為(f(n),該算法在最壞情況下所需的計算時間為(f(n).分析與解答：因此，Tmax(N) = (Tavg(N) = (f(n)=(f(n).第二章算法分析題2-3 設(shè)a0:n-1是已經(jīng)排好序的數(shù)組

4、。請改寫二分搜索算法，似的當(dāng)搜索元素x在數(shù)組中時，返回小于x的最大元素位置i和大于x的最小元素位置j。當(dāng)搜索元素在數(shù)組中時，i和j相同，均為x的位置。分許與解答：改寫二分搜索算法如下：typedef int TYPE_t;/* * Function name: BinarySearch * Parameters: * iIndex 代表i的位置，即最大元素位置; * jIndex代表j的位置，即最小元素位置; * aArr: 代表數(shù)組a,且有序 * xVar:代表元素x; * aLen: 代表數(shù)組元素個數(shù); * Return value: * 0: 執(zhí)行成功，最大元素位置和最小元素位置不等 *

5、 1: 執(zhí)行成功，最大元素位置和最小元素位置相等 */static int BinarySearch(TYPE_t aArr, int nLen, TYPE_t xVar, int *iIndex, int *jIndex) int left = 0; int right = nLen - 1; int middle = (left + right) / 2; while (left <= right) if (xVar = aArrmiddle) *iIndex = *jIndex = middle; return 1; if (xVar > aArrmiddle) left =

6、 middle + 1; else right = middle - 1; middle = (left + right) / 2; *iIndex = right; *jIndex = left; return 0;算法分析題2 6 對任何非零偶數(shù)n，總可以找到奇數(shù)m和正整數(shù)k，使得n = m * 2k.為了求出2個n階矩陣的乘積，可以把一個n階矩陣劃分成m×m個子矩陣，每個子矩陣2k×2k個元素。當(dāng)需要求2k×2k的子矩陣的積時，使用Strassen算法。設(shè)計一個傳統(tǒng)方法與Strasssen算法相結(jié)合的矩陣相乘算法，對于任何偶數(shù)n，都可以求出2個n階矩陣的乘積

7、。并分析算法的計算時間復(fù)雜度。分析與解答：將n階矩陣分塊為m×m的矩陣。用傳統(tǒng)方法求2個m階矩陣的乘積需要計算O(m3)次2個2k×2k矩陣的乘積。用Strassen矩陣乘法計算2個2k×2k的矩陣的乘積需要的計算時間為O(7k), 因此算法的計算時間為O(7k*m3).算法分析題2 - 9 設(shè)T0, n-1是n個元素的數(shù)組。對任一元素x，設(shè)S(x) = i | Ti = x . 當(dāng)|S(x) | > n/2時，稱x為T的主元素。設(shè)計一個線性時間算法，確定T0:n-1是否有一個主元素。 分析與解答：如果T有一個主元素x，則x是T的中位數(shù)。反之，如果T的中位數(shù)

8、不是T的主元素，則T沒有主元素。下面算法設(shè)計為在一個線性時間中找中位數(shù)：typedef int T;#define YES_MIDDLE_ELEMENT 1#define NO_MIDDLE_ELEMENT 0/* * Function name: * IsExistMiddleElement * Parameters: * aArr: 表示數(shù)組T0:n-1 * n: 表示數(shù)組長度 * x: 表示要判斷的數(shù)x，是否主元素 * *keyIndex: 表示主元素在數(shù)組中的下標(biāo) * * Return: * YES_MIDDLE_ELEMENT: 表示找到 * NO_MIDDLE_ELEMENT: 表

9、示沒有找到 */static int IsExistMiddleElement(T aArr, int n, T x, int *keyIndex) int middleKey = n / 2; int i = 0; for (i = 0; i < n; i+) if (aArri = x) && (i + 1) > middleKey) *keyIndex = i; return YES_MIDDLE_ELEMENT; *keyIndex = -1; return NO_MIDDLE_ELEMENT;算法分析題2-14 對所給元素存儲于數(shù)組中和存儲于鏈表中2中情形

10、，寫出自然合并排序算法。分析與解答：自然合并排序是合并排序算法的一種改進(jìn)。自然合并排序，對于初始給定的數(shù)組，通常存在多個長度大于1的已自然排好序的子數(shù)組段。例如，若數(shù)組a中元素為4,8,7,1,5,6,2,則自然排好序的子數(shù)組段有4,8, 3, 7, 1,5,6, 2.用一次對數(shù)組a的線性掃描就足以找出所有這些排好序的子數(shù)組段。然后將相鄰的排好序的子數(shù)組段兩兩合并，構(gòu)成更大的排好序的子數(shù)組段3,4,7,8, 1, 2,5,6.繼續(xù)合并相鄰排好序的子數(shù)組段，直至整個數(shù)組已經(jīng)排好序。算法設(shè)計及代碼實(shí)現(xiàn)：(1). 數(shù)組實(shí)現(xiàn)法：#define DEBUG 1typedef int type_t;sta

11、tic void DatasetMerge(type_t *arr, int left, int between, int right) int i, k; int begin1, end1, begin2, end2; type_t *tmpArr; begin1 = left; /*第一個排好序的初始位置*/ end1 = between; /*第一個排好序的結(jié)束位置*/ begin2 = between + 1; /*第二個排好序的初始位置*/ end2 = right; /*第二個排好序的結(jié)束位置*/ tmpArr = malloc(sizeof(type_t) * (right -

12、left + 1); if (!tmpArr) return; k = 0; /* * 比較兩個指針指向的元素，選擇相對小的元素放入合并空間 * 并移動指針到下一個位置 */ while (begin1 <= end1) && (begin2 <= end2) if (arrbegin1 < arrbegin2) tmpArrk = arrbegin1; begin1+; else tmpArrk = arrbegin2; begin2+; k+; /* ×如果第一個序列有剩余，直接拷貝到合并數(shù)組的序列中 */ while (begin1 <=

13、 end1) tmpArrk+ = arrbegin1+; /* *如果第二個序列有剩余，直接拷貝到合并數(shù)組的序列中 */ while(begin2 <= end2) tmpArrk+ = arrbegin2+; /* *拷貝臨時數(shù)組序列到原數(shù)組中 */ for (i = 0; i <= (right - left); i+) arrleft + i = tmpArri; free(tmpArr); void DatasetNatureMerge(type_t arr, int n) int *tmpArr; int i, k = 0; int s = 1; int group;

14、/*記錄分割組的數(shù)目*/ int count = 0; int left, between, right; int arrLen = n; /* *tmpArr 用來存儲數(shù)組元素下標(biāo)分割點(diǎn) */ tmpArr = (int*)malloc(n * sizeof(int); if (!tmpArr) return; memset(tmpArr, -1, (n * sizeof(int); /* * 存儲首分割點(diǎn) */ tmpArrk+ = 0; for (i = 0; i < arrLen - 1; i+) if (arri > arri+1) tmpArrk = i; k+; /*

15、 * 存儲尾分割點(diǎn) */ tmpArrk = n - 1; /* * k 和 group 分別記錄分割數(shù)組長度 */ group = k;#if DEBUG printf("n數(shù)組分割點(diǎn)為:n"); printf("t"); for (i = 0; i <= group; i+) if (i = 10) printf("nt"); printf("%d ", tmpArri); printf("n");#endif s = 1; for (group; group != 1; group

16、= (group % 2 = 0) ? (group / 2) : (group / 2 + 1) /* *合并次數(shù)，例如：5組合并需要兩次，4組合并也需要兩次 */ count = group / 2; /* *進(jìn)行第一次合并 */ left = 0; between = s; right = 2 * s; if (right > k) right = k; DatasetMerge(arr, tmpArrleft, tmpArrbetween, tmpArrright); /* * 進(jìn)行生下來的合并 */ for (i = 1; i < count; i+) left = ri

17、ght; between = left + s; right = between + s; if (right > k) right = k; DatasetMerge(arr, tmpArrleft + 1, tmpArrbetween, tmpArrright); s += s; free(tmpArr);(2). 鏈表實(shí)現(xiàn)法：#if LINKtypedef struct node *link_t;struct node int item; link_t next;link_t LinkMerge(link_t a, link_t b) link_t c, head; c = hea

18、d = malloc(sizeof(struct node); while (a != NULL) && (b != NULL) if (a->item < b->item) c->next = a; c = a; a = a->next; else c->next = b; c = b; b = b->next; c->next = (a = NULL) ? b : a; return head->next;link_t LinkNuturalMergesort(link_t t) link_t a, b; link_t u, v; QUEUE<link_t> Q; if (t = NULL | t->next = NULL) return t; for