作者CorruptAngel (微笑面具)
看板ACMCLUB
标题[问题]
时间Thu Oct 21 19:08:05 2004
现在有一个input 长度k 由很L个x 和 k-L 个yj组成 j = 1 , 2 , ... k-L
（第一个输入是x）
有另外一个大小是k的集合W 由L个z和 k-L 个yj组成 j = 1 , 2 , ... k-L
input开始读起 读到x则随机删除W中的一个元素 cost加1
如果读到yi 且yi还在集合W中 则删除yi ;
如果读到yi 且yi已经被删除 则随机删除一个元素 且cost加1
（随机：如果集合大小s里面每个元素被删除的机率是1/s）
证明 对於"任何的input"
k
E[cost] <= L * sigma 1/p
cost的期望值 p = 1
--
希望大家能帮忙想一下>///<
--
手写的出你的名字，但却渐渐忘记你的样子，
就算你不曾念过我的名字，但我也仍喜欢你。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.82
※ 编辑: CorruptAngel 来自: 140.112.30.82 (10/21 19:10)
※ 编辑: CorruptAngel 来自: 61.228.191.26 (10/21 20:39)