現在有一個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)