知识卡片

普通读书笔记卡 · 3727.b.1.a.2

二项式系数有熵界

理解等级:高级

当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约定处理。

这张卡片看不懂?

已有反馈 · 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