← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3596.c.3.a

忽略取整须多项式增长

理解等级:高级

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.