知识卡片

普通读书笔记卡 · 1289.g.5

常见增长阶的层次

理解等级:初级

对固定正幂与固定大于 1 的指数底数,多对数增长慢于任意正幂多项式,而多项式增长慢于指数;阶乘又有自己的更快增长界。

比较算法时先确认指数底数和幂次是否真为常数,再用这些层次。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 3 章 3.3 节“Polynomials”“Exponentials”“Logarithms”“Factorials”(`OEBPS/chapter003.xhtml`,式 3.13、3.24、3.25 等图片已核对)。 - 结论依据:原文分别证明指数快于任意多项式、多项式快于任意多对数,并给出 Stirling 近似及相关阶乘界。 - 原始内容:Thus, any exponential function with a base strictly greater than 1 grows faster than any polynomial function.