- 代码见prac222_SelectionSort
- 代码中，i=0开始第一次循环，i表示无序区中第一个元素，依次循环过后这个元素称为有序曲最后一个元素，则：
初始化： 当i=0时，有序区还没有元素，没有元素自然也可以认为是有序的，循环不变式成立；
保持： 假设数组A[1...j]当前是有序的，那么A[1...j]中的元素一定比数组中剩下的元素都小（不大于），下次迭代将会使A[j+1]交换到剩下元素中最小的元素，那么a[1...j+1]还是有序的，循环不定式成立
终止： 研究循环终止时发生什么。循环终止时，原数组中前n-1个元素都在有序曲，只有一个元素在无序区，而按照算法的特性无序区中的元素都大于等于有序区中的元素，故整个数组依然有序。算法成立。 - 因为根据算法特性，有序曲中的元素都小于等于无序区中的元素，只对前n-1个元素运行即可以保证整个数组有序。
- 不论最坏情况还是最好情况：
都需要进行n-1轮元素比较，每轮比较的次数为： n, n-1, ..., 2，总的比较次数为(n-1)*(n+2)/2，最好最坏都是：θ(n^2)
代码见prac213_linearSearch
假设要查找的元素等可能地为数组中的元素，则:
- 平均查找多少个元素？ -- (1 + 2 + ... + n)/n = (n+1)/2个。
- 最坏呢？ -- n个
- 都是θ(n)
不太明白习题的意思。
英文答案：Modify the algorithm so it tests whether the input satisfies some special-case condition and, if it does, output a pre-computed answer.
The best-case running time is generally not a good measure of an algorithm.
见Text2_3_MergeSort.java之new_merge()方法
- 当k=1时， n=2^k=2，等式成立。
- 假设k=i时，
T(n)=T(2^i) = 2T(2^i/2) + 2^i = 2^i x lg2^i 成立 - 则k=i+1时
T(n)=T(2^(i+1))=2xT(2^(i+1)/2) + 2^(i+1)
=2 x T(2^i) + 2^i x 2 //把等式2 T(2^i0 = 2^i x lg2^i代入
=2 x 2^i x lg2^i + 2^i x 2
=2^(i+1) x (lg2^i + 1)
= 2^(i+1) x (lg2^i + lg2)
=2^(i+1) x log2^(i+1)
证毕。
- 插入排序递归写法见 prac234_InsertSort_Recursive
- 递归式：
- n=1, 为常量c*1；
- n>1时，我们把递归过程分为分解、处理、合并三部分。
其中分解、合并部分都是n的线性函数，记为c1*n, c2*n, 可以合并为 c*n
处理部分，假设规模为n,当i=1...n时，最坏情况下的比较次数分别为
i 1 2 3 。。。n
比较次数 0 1 2 ... n-1
故全部比较次数为 0 + 1 + 2 + ... + n-1 = (n-1)(n-2)/2
可以记为(n-1)(n-2)/2 + c*n
综上，递归式为：
T(n) = c (n=1)
T(n) = (n-1)(n-2)/2 + c*n (n>1)
相当于处理部分从(n-1)(n-2)/2 + cn 变为 lg1+lg2+...+lg(n-1) +c*n，忽略c*n
即证明 lg1+lg2+...+lg(n-1) 是否等于nlgn
nlgn可以写成lgn + lgn + lgn
而lg1<lgn, lg2<lgn...
故能收敛到O(nlgn)
可以。
思想：
先用O(nlgn)算法对集合排序。
然后调用二分查找。
（当然用HashSet辅助的话，更快。）
代码： prac237_FindTwoElementsSum