算法设计与分析课后习题_第1页
算法设计与分析课后习题_第2页
算法设计与分析课后习题_第3页
算法设计与分析课后习题_第4页
算法设计与分析课后习题_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第一章1. 算法分析题算法分析题11 求下列函数的渐进表达式(1). 3n2 + 10n < 3n2 + 10n2 = 13n2 = O(n2)(2). n2 / 10 + 2n当n>5是,n2 < 2 n所以,当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) 因为:f(n

2、)=log(n2) = 2log(n); g(n) = log(n) + 5所以:f(n)=(log(n)+5) =(g(n)(2) 因为:log(n) < n ; f(n) = 2log(n); g(n)= n 所以:f(n) = O(g(n)(3) 因为:log(n) < n; f(n) = n; g(n) = log(n2) = 2log(n)所以;f(n) = (g(n)(4) 因为:f(n) = nlogn +n; g(n) = logn所以:f(n) =(g(n)(5) 因为: f(n) = 10; g(n) = log(10)所以:f(n) =(g(n)(6) 因为:

3、 f(n)=log2(n); g(n) = log(n)所以: f(n) =(g(n)(7) 因为: f(n) = 2n < 100*2n; g(n)=100n2; 2n > n 2所以: f(n) = (g(n)(8) 因为:f(n) = 2n; g(n) = 3 n; 2 n < 3 n所以: f(n) = O(g(n)习题19 证明:如果一个算法在平均情况下的计算时间复杂性为(f(n),该算法在最坏情况下所需的计算时间为(f(n).分析与解答:因此,Tmax(N) = (Tavg(N) = (f(n)=(f(n).第二章算法分析题2-3 设a0:n-1是已经排好序的数组

4、。请改写二分搜索算法,似的当搜索元素x在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x的位置。分许与解答:改写二分搜索算法如下:typedef int TYPE_t;/* * Function name: BinarySearch * Parameters: * iIndex 代表i的位置,即最大元素位置; * jIndex代表j的位置,即最小元素位置; * aArr: 代表数组a,且有序 * xVar:代表元素x; * aLen: 代表数组元素个数; * Return value: * 0: 执行成功,最大元素位置和最小元素位置不等 *

5、 1: 执行成功,最大元素位置和最小元素位置相等 */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 对任何非零偶数n,总可以找到奇数m和正整数k,使得n = m * 2k.为了求出2个n阶矩阵的乘积,可以把一个n阶矩阵划分成m×m个子矩阵,每个子矩阵2k×2k个元素。当需要求2k×2k的子矩阵的积时,使用Strassen算法。设计一个传统方法与Strasssen算法相结合的矩阵相乘算法,对于任何偶数n,都可以求出2个n阶矩阵的乘积

7、。并分析算法的计算时间复杂度。分析与解答:将n阶矩阵分块为m×m的矩阵。用传统方法求2个m阶矩阵的乘积需要计算O(m3)次2个2k×2k矩阵的乘积。用Strassen矩阵乘法计算2个2k×2k的矩阵的乘积需要的计算时间为O(7k), 因此算法的计算时间为O(7k*m3).算法分析题2 - 9 设T0, n-1是n个元素的数组。对任一元素x,设S(x) = i | Ti = x . 当|S(x) | > n/2时,称x为T的主元素。设计一个线性时间算法,确定T0:n-1是否有一个主元素。 分析与解答:如果T有一个主元素x,则x是T的中位数。反之,如果T的中位数

8、不是T的主元素,则T没有主元素。下面算法设计为在一个线性时间中找中位数:typedef int T;#define YES_MIDDLE_ELEMENT 1#define NO_MIDDLE_ELEMENT 0/* * Function name: * IsExistMiddleElement * Parameters: * aArr: 表示数组T0:n-1 * n: 表示数组长度 * x: 表示要判断的数x,是否主元素 * *keyIndex: 表示主元素在数组中的下标 * * 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 对所给元素存储于数组中和存储于链表中2中情形

10、,写出自然合并排序算法。分析与解答:自然合并排序是合并排序算法的一种改进。自然合并排序,对于初始给定的数组,通常存在多个长度大于1的已自然排好序的子数组段。例如,若数组a中元素为4,8,7,1,5,6,2,则自然排好序的子数组段有4,8, 3, 7, 1,5,6, 2.用一次对数组a的线性扫描就足以找出所有这些排好序的子数组段。然后将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组段3,4,7,8, 1, 2,5,6.继续合并相邻排好序的子数组段,直至整个数组已经排好序。算法设计及代码实现:(1). 数组实现法:#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; /*第一个排好序的结束位置*/ begin2 = between + 1; /*第二个排好序的初始位置*/ end2 = right; /*第二个排好序的结束位置*/ 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+; /* ×如果第一个序列有剩余,直接拷贝到合并数组的序列中 */ while (begin1 <=

13、 end1) tmpArrk+ = arrbegin1+; /* *如果第二个序列有剩余,直接拷贝到合并数组的序列中 */ while(begin2 <= end2) tmpArrk+ = arrbegin2+; /* *拷贝临时数组序列到原数组中 */ 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、/*记录分割组的数目*/ int count = 0; int left, between, right; int arrLen = n; /* *tmpArr 用来存储数组元素下标分割点 */ tmpArr = (int*)malloc(n * sizeof(int); if (!tmpArr) return; memset(tmpArr, -1, (n * sizeof(int); /* * 存储首分割点 */ tmpArrk+ = 0; for (i = 0; i < arrLen - 1; i+) if (arri > arri+1) tmpArrk = i; k+; /*

15、 * 存储尾分割点 */ tmpArrk = n - 1; /* * k 和 group 分别记录分割数组长度 */ group = k;#if DEBUG printf("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) /* *合并次数,例如:5组合并需要两次,4组合并也需要两次 */ count = group / 2; /* *进行第一次合并 */ left = 0; between = s; right = 2 * s; if (right > k) right = k; DatasetMerge(arr, tmpArrleft, tmpArrbetween, tmpArrright); /* * 进行生下来的合并 */ 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). 链表实现法:#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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论