大文件随机取K行[2013网易笔试]
1.给定一个巨大的文件（无法全部放入内存），如何从中选出k行，随处输出k行到文件中。
要求每一行出现的概率都相等。设计算法、说明思路，算法复杂度。
[解决办法]
假设一共有n行，用ai=0表示第i行没选，ai=1表示第i行选中，所以我们要求的就是序列a(n,k) = [a1,a2....,an]。
取[0, 1)的随机数R, 则a(n,k) = [0, a(n-1, k)] (如果 R>k/n) 或者 a(n,k) = [1, a(n-1, k-1)] (如果 R<=k/n)，由这个递推式就可以求出a1到an，边界条件是k=0，那么剩下的元素全为0，或者n=k，那么剩下的元素全为1。算法时间复杂度为O(n)
这个数学证明貌似难度比较高，搞不定
[解决办法]
蓄水池抽样 公式很容易推导
先把读到的前k个对象放入“水库”，对于第k+1个对象开始，以k/(k+1)的概率选择该对象，以k/(k+2)的概率选择第k+2个对象，以此类推，以k/m的概率选择第m个对象（m>k）。如果m被选中，则随机替换水库中的一个对象。最终每个对象被选中的概率均为k/n
[解决办法]
