知识卡片
常见增长阶的层次
对固定正幂与固定大于 1 的指数底数,多对数增长慢于任意正幂多项式,而多项式增长慢于指数;阶乘又有自己的更快增长界。
比较算法时先确认指数底数和幂次是否真为常数,再用这些层次。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 常见增长阶的层次
原书出处 · 1 处
- 第3章 运行时间的刻画 · 查看原书依据
Thus, any exponential function with a base strictly greater than 1 grows faster than any polynomial function.
参考来源
- 位置:《算法导论(第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.