}

设递归的时间效率为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的内层循环包括一次键值交换和一次序号递减,设一次赋值和一次序号递减的时间分别为ca和cd,那么算法

InsertSort2和算法InsertSort运行时间的比率是(3ca+cd)/(ca+cd)

习题5.2

22

1.a.(略) b.

4.

习题5.3 1.

DFS的栈状态:

退栈顺序: efgbcad 拓扑排序: dacbgfe b.

这是一个有环有向图.DFS 从a出发,?,遇到一条从e到a的回边.

4.能否利用顶点进入DFS栈的顺序(代替它们从栈中退出的顺序)来解决拓扑排序问题? Hints: 不能.

23

5. 对第1题中的有向图应用源删除算法.

拓扑序列: dabcgef

24