抱歉我忘了说明了_ _|| 这是某个演算法分析的一小部份... 所以可以假设k L足够大/__\ 阿阿阿阿阿阿阿~~~~~ 还有 我错了orz...是要证 <= 真的很抱歉>///< ※ 引述《scwg (void * I = NULL;)》之铭言： : ※ 引述《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: 61.228.191.26 ※ 编辑: CorruptAngel 来自: 61.228.191.26 (10/21 20:44)