算法分析与设计作业答案.doc

《算法分析与设计作业答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计作业答案第一章绪论一填空算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算2..算法具备五个重要特性：确定性、可实现性、数据输入、数据输出、有穷性3.要制定一个算法，一般要经过设计、确认、分析、编码、调试等阶段。4.算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。5．一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上。时间和空间资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。7.算法的时间复杂性函数用T(n)表示，它是问题的大小n的函数。8.n在不同的问题中有不同的表现形式。指出下列问题中n的计

2、量。1)在数组中找值为c的分量，n表示数组中分量的个数2)两个矩阵相乘,n表示矩阵的阶3)一个数表的排序，n表示数组中元数的个数4)遍历一棵二叉树，n表示树中的结点数9.最坏情况下的时间复杂性定义：W(n)=max{T(n，I)},I∈Dn10.平均情况下的时间复杂性定义：A(n)＝∑P(I)T(n，I)I∈Dn11.最具有可操作性和实际价值的是最坏情况下的时间复杂性定义复杂性。教材中没有特殊说明时，T(n)一般指的就是最坏情况下的时间复杂性定义。12．f(n)=O(g(n))表示当且仅当存在正的常数C和N0，使得对于所有的n>=N0，有f(n)<=c

3、g(n)。13.写出下列f(n)的渐进性态：1)f(n)=C0，为常数：f(n)=O(1)。2)f(n)=3n+2：f(n)=O(n)。3)f(n)=6×2n+n：f(n)=O(2n)。4)f(n)=nlogn：f(n)=O(nlogn)。二分析算法复杂性1.已知不重复且已经按从小到大排好的m个整数的数组A[L．m](为简单起见，设m＝2k，k是一个确定的非负整数)。对于给定的整数c，要求寻找一个下标i，使得A[i]=c,若找不到，则返回一个0。算法如下：proceduresearch(c)/*c是整型数*/{i←0;j←l;whileA[j]

4、dj

5、-1，花时间为：第二章分治法一.回答问题1．分治法的基本思想是什么？答：将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1

6、在A(1：9)中顺序存放着以下九个元素：-15，-6，0，7，9，23，54，82，101，用二分检索算法检索x=101是否在A中，需要比较几次？解：第一次执行循环体：mid=5，A[mid]

7、)，mid将数组分成大小为的两部分，递归调用原过程分别在两部分找max1、min1和max2、min2，分别花时间为，比较max1、max2和min1、min2找出max、min所花时间为2。因此递归方程为：。当n是2的幂时，即对于某个正整数k，n：2k，有T(n)：2T(n/2)+2＝2(2T(n/4)+2)+2=4T(n/4)+4+2……＝2k-1+2k-2＝3n/2-2所以：1.归并分类算法解：用T(n)表示归并排序所用的时间，两个子集递归调用归并排序过程所花时间：2T(n/2)，合并过程所用时间为cn，其中c是一个正数，则有递归方程：其中，是一

8、个常数。若n是2的方幂：，直接推导可得对于一般的整数n，我们可以假定，于是，所以3.汉诺塔问题