抱歉我忘了說明了_ _||
這是某個演算法分析的一小部份... 所以可以假設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)