知识卡片
忽略取整须多项式增长
Akra–Bazzi 递归式可含不同规模子问题,但不能无条件忽略取整。
若驱动函数满足多项式增长条件,常数倍改变自变量只使函数值变化常数倍,则向上或向下取整不改变解的 Θ 界。
常见多项式乘对数函数通常满足,指数函数不满足。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 分治策略 · 查看原书依据
When the driving function in an Akra-Bazzi recurrence satisfies the polynomial-growth condition, floors and ceilings don’t change the asymptotic behavior of the solution.
参考来源
- 位置:《算法导论(第4版)》第 4 章 4.6–4.7 节(`OEBPS/chapter004.xhtml`,文本字符 [80000, 85000);公式图 Art_P166–P230)。
- 结论依据:4.7 节定理 4.5 明确以 f 的 polynomial-growth condition 为前提,说明取整扰动不改变 Akra–Bazzi 递归解的渐近阶。
- 原始内容:When the driving function in an Akra-Bazzi recurrence satisfies the polynomial-growth condition, floors and ceilings don’t change the asymptotic behavior of the solution.