Introduction to Algorithms 3rd Edition
Part II - Sorting and Order Statistics
Chapter 9: Medians and Order Statistics
这一章主要是介绍查找问题：查找最大值、最小值，查找第n大的数等等。
很显然，查找最大值和最小值都需要遍历整个数组，因此时间复杂度是O(n)；如果同时查找最大值和最小值，是否需要遍历两遍数组呢？其实是不需要的，只需将原数组两两分组，每组分别比较，然后在n/2个较大的数里查找最大值，在剩下的n/2个数里查找最小值，总共的比较次数是3n/2，比遍历两次数组的2n-2要少n/2左右的比较次数。这也可以算是分治思想的应用。
对于查找第n大的数，如果是有大量的查询，可以先将原数组排序，然后直接选择即可，时间复杂度是O(nlgn)。如果只有少量的几次查询，需要在线性时间内完成呢？可以借鉴快速排序的思想，随机选择一个数，将原数组分成两份，判断是在前半部分还是后半部分查找，递推即可。可以证明，该算法平均情况下的时间复杂度是O(n)，但是最坏情况下的时间复杂度是O(n^2)。
因此，能否找到一种在最坏情况下是O(n)的查找算法呢？答案是肯定的。算法思路如下。不妨设原问题的时间复杂度是W(n)，那么第2行的时间复杂度是W(n/5)，再次递归时最坏情况下的时间复杂度是W(7n/10)，因此W(n) <= W(n/5) + W(7n/10) + cn <= cn + 9n/10 + 81n/100 + ... = O(n)
SELECT(S, k)
1 将S划分成5个一组，共n_M = upper(n/5)组
2 对每组的5个数进行排序，找中位数，n_M个中位数放到集合M
3 m* = SELECT(M, upper(|M|/2)) 将S中的数划分成A, B, C, D四个集合
4 将A和D中的每个元素与m*比较，小的构成S1，大的构成S2
5 S1 = S1 U C, S2 = S2 U B
6 if k = |S1| + 1, return m*
7 else if k <= |S1|, return SELECT(S1, k)
8 else, return SELECT(S2, k - |S1| - 1)
其实，这个算法在从理论上来说是非常漂亮的，但是太不优美了，太复杂了，编程实现也不太容易，虽然是O(n)的复杂度，但是隐藏的系数很大。而且，现实中，在一个很大的集合中只查找一次的情况不太常见，因此该算法在实际上用途有限。重点仍是掌握排序算法，彻底掌握插入排序、归并排序、堆排序和快速排序。
Exercises
9.1-1
将原数组两两分组，每组分别比较，将较大的数记录在较小的数指向的链表中，递归，最后最小的数指向的链表有upper(lg(n))个数，由于找到最小的数需要n-1次比较，因此总共需要的比较次数是n+upper(lg(n))-2
9.3-1
每组7个仍然有效，但是每组3个就不成立。至少需要5。
9.3-3
每次分割选择中位数
9.3-4
?
9.3-5
找出中位数，将数组划分，再在其中某个数组中查找即可。T(n) <= T(n/2) + O(n) = O(n)
9.3-7
找出第n/2-k/2大的和第n/2+k/2大的数，然后遍历找出在其中的数即可
9.3-8
比较X[n/2]和Y[n/2]，如果X[n/2]>Y[n/2]，那么再比较X[n/4]和Y[3n/4]，依此类推，每次减少一半的数，因此T(n) = T(n/2) + 1 = O(lg(n))
9.3-9
可以证明，当pipeline在所有well的y值的中位数的位置，总长是最小的。因此就是找中位数的问题。
Problems
9-1
a. 用归并排序或者堆排序，时间复杂度是O(nlgn)
b. 建堆时间复杂度是O(n)，每次选出最大值，调整堆复杂度O(lgn)，因此总的时间复杂度是O(n + ilgn)
c. 选出第i大的数O(n)，分割O(n)，排序O(ilgi)，总时间复杂度是O(n + ilgi)
9-2
a. 显然
b. 对x排序，然后累加w值直至1/2即可
c. 选出x的中位数，将x分割，累加每部分中的x值，对大于1/2的部分递归，T(n) = T(n/2+1) + O(n) = O(n)
d. 略，有点复杂
e. 由于x和y互不影响，因此对x和y分别找出weighted median，即可确定坐标。
No comments:
Post a Comment