※ 引述《scwg (void * I = NULL;)》之銘言： : ※ 引述《CorruptAngel (微笑面具)》之銘言： : : 抱歉我忘了說明了_ _|| : : 這是某個演算法分析的一小部份... 所以可以假設k L足夠大/__\ : hmm... 那我證的看起來就算 L, k - L 有是 0 的都 ok.. : : 阿阿阿阿阿阿阿~~~~~ : : 還有 我錯了orz...是要證 <= : : 真的很抱歉>///< : L = 0 時明顯兩邊都是 0 : L = k 時明顯右邊 L <= L * (1 + ...) : 好, 然後設當 k, L 較小時不等式成立 : 如果第一個 input 是 x (probability = L/k) : selected z (probability = L/k): E(k, L) = 1 + E(k - 1, L - 1) : selected yi (probability = (k-L)/k): 把 yi 換成 x, 那就變成 (k - 1, L) 的問題 : E(k, L) = 1 + E(k - 1, L) : 如果第一個 input 是 yi (probability = (L-k)/k) : 直接刪掉, E(k, L) = E(k - 1, L) 這幾行我改了一些東西 大概我又沒說清楚.. "對於任意的input" 是說不管怎樣的input來不等式都會對 也就是不行算對所有input的期望值(不能把input算進期望值,也就是要worst case) 不過學長你這個證明的助益很大＠＿＠ 我在想看看.. : L 2 L 2 L(k - L) : 所以 E(k, L) = (---) + (---) E(k - 1, L - 1) + ---------- : k k k^2 : L(k - L) k - L : + ---------- E(k - 1, L) + ------- E(k - 1, L) : k^2 k : L L^2 k - 1 1 k^2 - L^2 k - 1 1 : <= --- + ----- (L - 1) sigma --- + ----------- L sigma --- : k k^2 p = 1 p k^2 p = 1 p : L k - 1 1 L^2 k - 1 1 : = --- + L sigma --- - ----- sigma --- : k p = 1 p k^2 p = 1 p : k 1 : <= L sigma --- : p = 1 p : 不知道有沒有問題? -- 手寫的出妳的名字，但卻漸漸忘記妳的樣子， 就算妳不曾唸過我的名字，但我也仍喜歡妳。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.191.26 ※ 編輯: CorruptAngel 來自: 61.228.191.26 (10/21 21:44)