知识卡片
阿克拉巴齐解不等规模递归
Akra–Bazzi 方法处理 T(n)=f(n)+ΣaᵢT(n/bᵢ) 等不等规模分治:aᵢ>0 表示第 i 类子问题的数量系数,bᵢ>1 表示其规模缩小为原来的 1/bᵢ,f(n) 是本层非递归工作。
- 先求唯一的
p,使Σaᵢ/bᵢ^p=1; - 再由
Θ(n^p(1+∫₁ⁿ f(x)/x^(p+1)dx))得解。
使用取整版递归时,还须核对驱动函数的多项式增长条件。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 分治策略 · 查看原书依据
Such a p always exists, because when p → –∞, the sum goes to ∞; it decreases as p increases; and when p → ∞, it goes to 0.
参考来源
- 位置:《算法导论(第4版)》第 4 章 4.6–4.7 节(`OEBPS/chapter004.xhtml`,文本字符 [80000, 85000);公式图 Art_P166–P230)。
- 结论依据:4.7 节公式图 Art_P226 给出 Σᵢaᵢ/bᵢ^p=1,Art_P227 给出 T(n)=Θ(n^p(1+∫₁ⁿ f(x)/x^(p+1)dx));定理 4.5 的多项式增长条件约束取整扰动。
- 原始内容:Such a p always exists, because when p → –∞, the sum goes to ∞; it decreases as p increases; and when p → ∞, it goes to 0.