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