Else return min{ClosestNumber(A[l… (l+r)/2 ]), ClosestNumber(A[ (l+r)/2 ...r]) A[ (l+r)/2 +1]－A[ (l+r)/2 ] } 设递归的时间效率为T(n): 对n=2k, 则: T(n)=2T(n/2)+c 利用主定理求解.T(n)=Θ(n) 2.(题略)
21
习题5.1
2.a.设计一个递归的减一算法,求n个实数构成的数组中最小元素的位置. b.确定该算法的时间效率,然后把它与该问题的蛮力算法作比较
Algorithms MinLocation(A[0..n-1])
//find the location of the smallest element in a given array //an array A[0..n-1] of real numbers
//An index of the smallest element in A[0..n-1] if n=1 return 0
else temp←MinLocation(A[0..n-2])
if A[temp]
时间效率分析见习题2.4中8 C(n)=C(n-1)+1 for n>1 C(1)=0
4.应用插入排序对序列example按照字母顺序排序
5.a.对于插入排序来说,为了避免在内部循环的每次迭代时判断边界条件j>=0,应该在待排序数组的第一个元素前放一个什么样的限位器? b.带限位器版本和原版本的效率类型相同吗?
解: a. 应该在待排序数组的第一个元素前放-∞或者小于等于最小元素值的元素. b. 效率类型相同.对于最差情况(数组是严格递减):
7.算法InsertSort2(A[0..n-1]) for i←1 to n-1 do
j←i-1
while j>=0 and A[j]>A[j+1] do swap(A[j],A[j+1]) j←j+1
分析:在教材中算法InsertSort的内层循环包括一次键值赋值和一次序号递减,而算法InsertSort2的内层循环包括一次键值交换和一次序号递
22
减,设一次赋值和一次序号递减的时间分别为ca和cd,那么算法
InsertSort2和算法InsertSort运行时间的比率是(3ca+cd)/(ca+cd)
习题5.2 1.a.(略) b.
4.
习题5.3 1.
DFS的栈状态:
退栈顺序: efgbcad 拓扑排序: dacbgfe b.
23
这是一个有环有向图.DFS 从a出发,?,遇到一条从e到a的回边.
4.能否利用顶点进入DFS栈的顺序(代替它们从栈中退出的顺序)来解决拓扑排序问题? Hints: 不能.
5. 对第1题中的有向图应用源删除算法.
拓扑序列: dabcgef
24
习题5.4
4.下面是生成排列的B.Heap算法. 算法HeapPermute(n)
//实现生成排列的Heap算法
//输入:一个正整数n和一个全局数组A[1..n] //输出:A中元素的全排列
If n=1
Write A Else
For i←1 to n do HeapPermute(n-1) If n is odd
Swap A[1] and A[n] Else swap A[i] and A[n] 对于n=2,3,4的情况,手工跟踪该算法. 解:对于n=2 for i=1 do
heappermute(1）{write A即12}
这时n not odd, so do A[1]与A[2]互换，A=21
for i=2 do
heappermute(1）{write A即21}
对于n=3 For i=1 do
Heappermute(2){ heappermute(1) write A 即123 这时2 not odd,so,do A[1]与A[2]
互换，A=213
heappermute(1) write A 即213 这时 2 not odd, do A[2]与A[2]互换，A=213 }
由于 3 is odd,so do A[1]与A[3]互换,A=312
For i=2 do
Heappermute(2){ heappermute(1) write A 即312 这时2 not odd,so,do A[1]与A[2]
互换，A=132
heappermute(1) write A 即132 这时 2 not odd, do A[2]与A[2]互换，A=231 }
由于 3 is odd,so do A[1]与A[3]互换,A=231
For i=3 do
Heappermute(2) { heappermute(1) write A 即231 这时2 not odd,so,do A[1]与A[2]
互换，A=321
heappermute(1) write A 即321 这时 2 not odd, do A[2]与A[2]互换，A=321 }
由于 3 is odd,so do A[1]与A[3]互换,A=123
n=4的的情况:
25