知识卡片
二项式系数有熵界
当k=λn且0≤λ≤1时,附录给出
C(n,k) ≤ 2^(nH(λ)),
其中二元熵函数H(λ)=−λ lg λ−(1−λ)lg(1−λ),lg以2为底。这个界把组合数的指数增长率写成H(λ):λ=1/2时H最大为1,得到中央组合数不超过2ⁿ;λ接近0或1时指数率更小。
它用于估计组合爆炸;边界λ=0或1时按0log0=0约定处理。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 二项式系数有熵界
原书出处 · 1 处
- 附录C 计数与概率 · 查看原书依据
For k = λn, where 0 ≤ λ ≤ 1, we can rewrite this bound as where is the (binary) entropy function and where, for convenience, we assume that 0 lg 0 = 0, so that H(0) = H(1) = 0. Exercises
参考来源
- 位置:《算法导论(第4版)》附录C《计数与概率》(OEBPS/appendix003.xhtml,文本字符[5000,10000))。
- 结论依据:附录C.1及原书公式图 Art_P1649.jpg、Art_P1650.jpg(式C.8):当整数 k=λn、0≤λ≤1 时,C(n,k)≤2^{nH(λ)},H(λ)=−λlgλ−(1−λ)lg(1−λ)。原文明确约定 0lg0=0,故 H(0)=H(1)=0;这是上界而非一般等式。
- 原始内容:For k = λn , where 0 ≤ λ ≤ 1, we can rewrite this bound as where is the (binary) entropy function and where, for convenience, we assume that 0 lg 0 = 0, so that H (0) = H (1) = 0. Exercises