作者scwg (void * I = NULL;)
看板ACMCLUB
标题Re: [问题]
时间Thu Oct 21 21:01:44 2004
※ 引述《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 x (probability = L/k): E(k, L) = 1 + E(k - 1, L - 1)
selected zi (probability = 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)
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: 140.112.30.20