习题2.6
1. 考虑下面的排序算法,其中插入了一个计数器来对关键比较次数进行计数. 算法SortAnalysis(A[0..n-1])
//input:包含n个可排序元素的一个数组A[0..n-1] //output:所做的关键比较的总次数 count←0
for i←1 to n-1 do 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 A[j+1]←v return count
比较计数器是否插在了正确的位置?如果不对,请改正. 解:应改为:
算法SortAnalysis(A[0..n-1])
//input:包含n个可排序元素的一个数组A[0..n-1] //output:所做的关键比较的总次数 count←0
for i←1 to n-1 do 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
9
习题3.1 4. a.设计一个蛮力算法,对于给定的x0,计算下面多项式的值: 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 M(n)???1??i?i?0j?1i?0ninn(n?1)??(n2) 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.应用选择排序对序列example按照字母顺序排序. 10
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.
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. 11 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:每次都从这些少见字符开始比较,如果匹配, 则向左边和右边进行其它字符的比较. 12