中国科技大学：算法基础习题1

2.2.1: 2.2.2: 参考算法如下 1 Select-sort(A,n) 2 for i←1 to n-1 3 min←A[i] 4 index←i 5 for j←i+1 to n 6 if A[j]< min 7 index←j 8 min←A[j] 9 if index i 10 A[index]←A[i] 11 A[i]←min loop invariant: 从A[1]到A[j-1]，这j-1个数是排好序的，并且是A中最小的j-1个数。 Best-case: Worst-case: 因为不管是最好情况，还是最坏情况，两层循环的复杂度都是一样的。 许多同学在第8行中，没有将min的值及时更新。这一点需要注意。 另外，许多同学都没有对loop invariant 进行 2.3.3: 证明如下 （采用数学归纳法） （1） 当k＝1时，n=2，显然有T（n）=nlgn （2） 假设当k＝i时公式成立，即T（n）=nlgn= ， 则当k＝i+1时，即n= 时， T（n）= T（ ）= 2 T（ ）+ = i + = (i+1) = lg = n lgn 综上可得：T（n）=nlgn 2.3.4: 或者 在n=1时T(n)=c ，c示常量级，或 都可以，不要写成1，有些同学将n从2开始，没有将n为1的情况包含进去。 2.3.6: 不能 虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有降下来，所以最坏情况下该算法的时间复杂度依然是 ，不能降为 2.3.7: 算法思想：首先要对n个数进行排序，用快排复杂度为 ，然后在在排序后的数组中查找是否存在两数之和为x。 查找可以用下面的，假设排序后数组中元素为非降序列： Search(A,n,x) QuickSort(A,n); i←1; j←n; while A[i]+A[j] x and i