zcc1307 于 2012-11-18 15:29:18发表:
这样行不行： 一直维护一个大小为100的池，假设这是一个在线算法： 新来一个记录（假设为第i(i>100)条），就以100/i概率将这个记录加进来,同时以1/100的概率把池子里的一条记录踢掉。 归纳法证明是保持均匀的：i=100作为归纳基础显然成立。 归纳步骤：1.第i条记录以概率100/i出现。2.对j所以能保证永远是均匀的。
weidrson 于 2012-11-18 08:53:35发表:
帮你顶一下
zcc1307 于 2012-11-18 15:29:18发表:
这样行不行：所以能保证永远是均匀的。
一直维护一个大小为100的池，假设这是一个在线算法：
新来一个记录（假设为第i(i>100)条），就以100/i概率将这个记录加进来,同时以1/100的概率把池子里的一条记录踢掉。
归纳法证明是保持均匀的：i=100作为归纳基础显然成立。
归纳步骤：1.第i条记录以概率100/i出现。2.对j
weidrson 于 2012-11-18 08:53:35发表:
帮你顶一下