知识卡片
主定理有递归式形状要求
主定理处理每次产生 a 个、各为原规模 1/b 的子问题,另有分解与合并代价 f(n) 的递归式。
子问题规模不等时,不能机械代入这三个参数;可先用递归树理解成本,再考虑更一般的 Akra–Bazzi 方法。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 分治策略 · 查看原书依据
It provides bounds for recurrences of the form T (n) = aT (n/b) + f (n), where a > 0 and b > 1 are constants and f (n) is a given “driving” function.
参考来源
- 位置:《算法导论(第4版)》第 4 章“Solving recurrences”(`OEBPS/chapter004.xhtml`,文本字符 [10000, 15000))。
- 结论依据:原文分别列出代入法、递归树、主定理与 Akra–Bazzi 法,并给出主定理的递归式形状。
- 原始内容:It provides bounds for recurrences of the form T ( n ) = aT ( n / b ) + f ( n ), where a > 0 and b > 1 are constants and f ( n ) is a given “driving” function.