《算法设计与分析课后习题》由会员分享，可在线阅读，更多相关《算法设计与分析课后习题（8页珍藏版）》请在金锄头文库上搜索。
1、第一章 1 算法分析题 算法分析题1 1 求下列函数的渐进表达式 1 3n 2 10n 5 是 n 2 1 时 n 2 10 2 n 故 n 2 10 2 n 2 n 2 n 2 2 n O 2 n 3 21 1 n 21 1 22 O 1 4 log n 3 3log n O log n 5 10log 3 n 10log3 n O n 算法分析题1 6 1 因为 f n log n 2 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
2、 log n 2 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 因为 f n log 2 n g n log n 所以 f n g n 7 因为 f n 2 n n 2 所以 f n g n 8 因为 f n 2 n g n 3 n 2 n 3 n 所以 f n O g n 习题 1 9 证明 如果一个算法在平均情况下的计算时间复杂性为 f n 该算法在最坏情况 下所需的计算时间为 f n 分析与解答 因此 Tmax N Tavg N f n f n 第二章
3、算法分析题 2 3 设 a 0 n 1 是已经排好序的数组 请改写二分搜索算法 似的当搜索元素 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 执行成功 最
4、大元素位置和最小元素位置不等 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 aArr middle left middle 1 else right middle 1 middle left right 2 iIndex right jIndex left return 0 算法分析题2 6 对任何非零偶数n 总可
5、以找到奇数m 和正整数k 使得 n m 2 k 为了 求出 2 个 n 阶矩阵的乘积 可以把一个n 阶矩阵划分成m m 个子矩阵 每个子矩阵2 k 2 k 个元素 当需要求2 k 2 k 的子矩阵的积时 使用 Strassen算法 设计一个传统方法 与 Strasssen算法相结合的矩阵相乘算法 对于任何偶数n 都可以求出2 个 n 阶矩阵的乘 积 并分析算法的计算时间复杂度 分析与解答 将 n 阶矩阵分块为m m 的矩阵 用传统方法求2 个 m 阶矩阵的乘积需要计算O m 3 次 2 个 2 k 2 k 矩阵的乘积 用 Strassen矩阵乘法计算2 个 2 k 2 k 的矩阵的乘积需要的计
6、算 时间为 O 7 k 因此算法的计算时间为O 7 k m 3 算法分析题2 9 设 T 0 n 1 是 n 个元素的数组 对任一元素x 设 S x i T i x 当 S x n 2 时 称 x 为 T 的主元素 设计一个线性时间算法 确定T 0 n 1 是否有一个主元 素 分析与解答 如果 T 有一个主元素x 则 x 是 T 的中位数 反之 如果T的中位数不是T的主元素 则T 没有主元素 下面算法设计为在一个线性时间中找中位数 typedef int T define YES MIDDLE ELEMENT 1 define NO MIDDLE ELEMENT 0 Function name
7、 IsExistMiddleElement Parameters aArr 表示数组 T 0 n 1 n 表示数组长度 x 表示要判断的数x 是否主元素 keyIndex 表示主元素在数组中的下标 Return YES MIDDLE ELEMENT 表示找到 NO MIDDLE ELEMENT 表示没有找到 static int IsExistMiddleElement T aArr int n T x int keyIndex int middleKey n 2 int i 0 for i 0 i middleKey keyIndex i return YES MIDDLE ELEMENT
8、keyIndex 1 return NO MIDDLE ELEMENT 算法分析题2 14 对所给元素存储于数组中和存储于链表中2 中情形 写出自然合并排序算 法 分析与解答 自然合并排序是合并排序算法的一种改进 自然合并排序 对于初始给定的数组 通常存在 多个长度大于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 继续合并相邻排好序的子
9、数组段 直至整个数组已经排好序 算法设计及代码实现 1 数组实现法 define DEBUG 1 typedef int type t static 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
10、sizeof type t right left 1 if tmpArr return k 0 比较两个指针指向的元素 选择相对小的元素放入合并空间 并移动指针到下一个位置 while begin1 end1 begin1 else tmpArr k arr begin2 begin2 k 如果第一个序列有剩余 直接拷贝到合并数组的序列中 while begin1 end1 tmpArr k arr begin1 如果第二个序列有剩余 直接拷贝到合并数组的序列中 while begin2 end2 tmpArr k arr begin2 拷贝临时数组序列到原数组中 for i 0 i righ
11、t left i arr left i tmpArr i free tmpArr void DatasetNatureMerge type t arr int n int tmpArr int i k 0 int s 1 int group 记录分割组的数目 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 存储首分割点 tmpArr k 0 for i
12、0 i arr i 1 tmpArr k i k 存储尾分割点 tmpArr k n 1 k 和 group 分别记录分割数组长度 group k if DEBUG printf n数组分割点为 n printf t for i 0 i k right k DatasetMerge arr tmpArr left tmpArr between tmpArr right 进行生下来的合并 for i 1 i k right k DatasetMerge arr tmpArr left 1 tmpArr between tmpArr right s s free tmpArr 2 链表实现法 if
13、 LINK typedef 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 head malloc sizeof struct node while a NULL 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 Q if t NULL t next NULL return t for u t t NULL t u while u v u u u next v next NULL Q ENQUEUE t Q DEQUEUE t while Q EMPTY Q ENQUEUE t Q DEQUEUE a Q DEQUEUE b t LinkMerge a b return t endif
