※ 引述《CorruptAngel (微笑面具)》之铭言： : 现在有一个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 在花了很长的时间找我在数归中的计算错误後, 我试着用 (k, L) = (2, 1) 来证这是错的 @@ 一个 x 一个 y1 所以有一半的机会第一个 input 是 x 如果 W 中选出 x: 下次出现 y1, total cost = 1 如果选出 y1: 下次出现 y1, 又要再加一个 cost, total cost = 2 一半的机会第一个 input 是 y1 这次会把 y1 删掉, 下次出现 x, total cost = 1 1 1 1 所以 E[cost] = --- * 1 + --- * 2 + --- * 1 = 1.25 4 4 2 k 1 1 但是 L * sigma --- = 1 * (1 + ---) = 1.5 @@ p = 1 p 2 --- 不知道是不是对 input 的假设有误? 还是哪里犯了机率计算上的错? --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.20 ※ 编辑: scwg 来自: 140.112.30.20 (10/21 20:32)