※ 引述《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)