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
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
所给算法的时间复杂度为
，许多同学只是写了伪代码，没有对算法的时间复杂度进行分析。另外一点需注意的是应指出选择哪种排序算法，并不是所有的排序的时间复杂度都是
。
_1188472972.unknown
_1188987141.unknown
_1188889810.unknown
_1188472429.unknown
_1188472644.unknown
_1188472666.unknown
_1188472945.unknown
_1188472576.unknown
_1188465056.unknown
_1188466395.unknown
_1188466441.unknown
_1188425650.unknown
_1188427517.unknown
_1188428054.unknown
_1188425676.unknown
_1188414607.unknown
浙公网安备 33021202002483