知识卡片

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

主定理按分水岭分三类

理解等级:中级

对递归式 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 与分水岭函数之间存在多项式级差距。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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 .