v←A[i] j←i-1 while j>0 and A[j]>v do count←count+1 A[j+1]←A[j] j←j+1 if j>=0 count=count+1 A[j+1]←v return count 习题3.1 04. a.设计一个蛮力算法,对于给定的x,计算下面多项式的值: P(x)=anxn+an-1xn-1+…+a1x+a0 并确定该算法的最差效率类型. b.如果你设计的算法属于Θ(n2),请你为该算法设计一个线性的算法. C.对于该问题来说,能不能设计一个比线性效率还要好的算法呢? 解: a. Algorithms BruteForcePolynomialEvaluation(P[0..n],x) //由高幂到低幂用蛮力法计算多项式p在给定点x的值 //输入:P[0..n]是多项式按低幂到高幂的常系数,以及定值x //输出: 多项式p在给定点x的值 p=0.0 for i=n to 0 do power=1 for j=1 to i do power=power*x p=p+P[i]*power return p 算法效率分析: 基本操作:两个数相乘,且M(n)仅依赖于多项式的阶n ninM(n)??i?0?1?j?1?i?0i?n(n?1)2??(n) 2b. tha above algorithms is very inefficient, because we recompute powers of x again and again as if there were no relationship among them.In fact ,we can move from the lowest term to the highest and compute xi by using xi-1. Algorithms BetterBruteForcePolynomialEvaluation(P[0..n],x) //由高幂到低幂用蛮力法计算多项式p在给定点x的值 //输入:P[0..n]是多项式按低幂到高幂的常系数,以及定值x //输出: 多项式p在给定点x的值 P=P[0] power=1 for i←1 to n do power←power*x p←p+P[i]*power
return p
基本操作乘法运算总次数M(n):
M(n)??2?2n??(n)
i?1nc.不行.因为计算任意一个多项式在任意点x的值,都必须处理它的n+1 个系数.例如: (x=1,p(x)=an+an-1+..+a1+a0,至少要做n次加法运算) 5.应用选择排序对序列E,X,A,M,P,L,E按照字母顺序排序.
6.选择排序是稳定的吗?(不稳定)
7.用链表实现选择排序的话,能不能获得和数组版相同的Θ(n2)效率?
Yes.Both operation—finding the smallest element and swapping it –can be done as efficiently with the linked list as with an array.
8.应用冒泡排序对序列E,X,A,M,P,L,E按照字母顺序排序.
9.a.请证明,如果对列表比较一遍之后没有交换元素的位置,那么这个表已经排好序了,算法可以停止了.
b.结合所做的改进,为冒泡排序写一段伪代码. c.请证明改进的算法最差效率也是平方级的. Hints:
a. 第i趟冒泡可以表示为:
如果没有发生交换位置,那么:
b.Algorithms BetterBubblesort(A[0..n-1])
//用改进的冒泡算法对数组A[0..n-1]排序 //输入:数组A[0..n-1]
//输出:升序排列的数组A[0..n-1]
count←n-1 //进行比较的相邻元素对的数目 flag←true //交换标志 while flag do flag←false
for i=0 to count-1 do if A[i+1]
swap(A[i],A[i+1]) flag←true count←count-1
c最差情况是数组是严格递减的,那么此时改进的冒泡排序会蜕化为原来的冒泡排序.
10.冒泡排序是稳定的吗?(稳定) 习题3.2
1. 对限位器版的顺序查找算法的比较次数:
a. 在最差情况下
b. 在平均情况下.假设成功查找的概率是p(0<=p<=1) Hints:
a. Cworst(n)=n+1
b. 在成功查找下,对于任意的I,第一次匹配发生在第i个位置的可能性是p/n,
比较次数是i.在查找不成功时,比较次数是n+1,可能性是1-p.
6.给出一个长度为n的文本和长度为m的模式构成的实例,它是蛮力字符串匹配算法的一个最差输入.并指出,对于这样的输入需要做多少次字符比较运算.
Hints:
文本:由n个0组成的文本
模式:前m-1个是0,最后一个字符是1 比较次数: m(n-m+1)
7.为蛮力字符匹配算法写一个伪代码,对于给定的模式,它能够返回给定的文本中所有匹配子串的数量.
Algorithms BFStringmatch(T[0..n-1],P[0..m-1]) //蛮力字符匹配
//输入:数组T[0..n-1]—长度为n的文本,数组P[0..m-1]—长度为m的模式 //输出:在文本中匹配成功的子串数量 count←0
for i←0 to n-m do j←0
while j count←count+1 return count 8.如果所要搜索的模式包含一些英语中较少见的字符,我们应该如何修改该蛮力算法来利用这个信息. Hint:每次都从这些少见字符开始比较,如果匹配, 则向左边和右边进行其它字符的比较. 习题3.4 8.解释一下如何对排序问题应用穷举查找，并确定这种算法的效率类型。 答：生成给定元素的一个排列，通过连续比较它们之间的元素，检查他们是否符合排序的要求。如果符合就停止，否则重新生成新的排列。 最差情况生成排列的个数是n！，每趟连续元素比较次数为n-1次。所以效率类型为O（n！（n-1））。 9.幻方 一个n阶幻方是把从1到 n2的整数填入一个n阶方阵，每个整数只出现一次，使得每一行，每一列，每一条主对角线的和都相等。 a.证明：如果一个n阶幻方存在的话，所讨论的和一定等于n(n2+1)/2。 答：令s为n阶幻方的每一行的和。则把从1到 n2的整数求和可得如下式子 由上式可得： 习题4.1 1.a.为一个分治算法编写伪代码,该算法求一个n个元素数组中最大元素的位置. b.如果数组中的若干个元素都具有最大值,该算法的输出是怎样的呢? c.建立该算法的键值比较次数的递推关系式并求解. d.请拿该算法与解同样问题的蛮力算法做一个比较 解:a. Algorithms MaxIndex(A[l..r]){ Input:A portion of array A[0..n-1] between indices l and r(l≤r) Output: The index of the largest element in A[l..r] if l=r return l else temp1←MaxIndex(A[l..(l+r)/2]) temp2←MaxIndex(A[(l+r)/2..r]) if A[temp1]≥A[temp2] return temp1 else return temp2 } b.返回数组中位于最左边的最大元素的序号. c.键值比较次数的递推关系式: C(n)=C( n/2 )+C( n/2 )+1 for n>1 C(1)=0 设n=2k，C(2k)=2C(2k-1)+1 =2[2 C(2k-2)+1]+1=22C(2k-2)+2+1 =2[22C(2k-3)+1]+2+1=23C(2k-3)+ 22+2+1 =... =2iC(2k-i)+ 2i-1+2 i-2 +...+2+1 =... =2kC(2k-k)+ 2k-1+2 k-2 +...+2+1=2k－1=n-1 可以证明C(n)=n-1对所有n>1的情况都成立（n是偶数或奇数） d.比较的次数相同，但蛮力算法不用递归调用。 2、a.为一个分治算法编写伪代码，该算法同时求出一个n元数组的最大元素和最小元素的值。 b.请拿该算法与解同样问题的蛮力算法做一个比较。 c.请拿该算法与解同样问题的蛮力算法做一个比较。 解答： a.同时求出最大值和最小值，只需要将原数组一分为二，再使用相同的方法找出这两个部分中的最大值和最小值，然后经过比较就可以得到整个问题的最大值和最小值。