知识卡片
主定理按分水岭分三类
对递归式 T(n)=aT(n/b)+f(n),T(n) 是规模为 n 的总成本,a≥1 是子问题数,b>1 是规模缩小倍数,f(n) 是递归调用之外的工作量。令分水岭函数 w=n^log_b a:
- 若
f(n)=O(w/n^ε),叶子主导,T(n)=Θ(w); - 若
f(n)=Θ(w log^k n)且k≥0,递归各层的代价累加后使对数因子增加一阶,T(n)=Θ(w log^(k+1)n); - 若
f(n)=Ω(wn^ε),且存在常数c<1,使足够大的n都满足正则条件a f(n/b)≤c f(n),则根主导,T(n)=Θ(f(n))。
其中 ε 必须是正常数;第一、三类都要求 f 与分水岭函数之间存在多项式级差距。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 分治策略 · 查看原书依据
In each of the three cases, we compare the driving function f (n) to the watershed function .
参考来源
- 位置:《算法导论(第4版)》第 4 章 4.5 节(`OEBPS/chapter004.xhtml`,文本字符 [55000, 60000);公式图 Art_P129–P158)。
- 结论依据:定理 4.1 的三种情形分别用 `f(n)=O(w/n^ε)`、`f(n)=Θ(w log^k n)` 和 `f(n)=Ω(wn^ε)` 比较驱动函数与分水岭函数,并为第三类附加正则条件;各情形有各自的 Θ 解。
- 原始内容:In each of the three cases, we compare the driving function f ( n ) to the watershed function .