知识卡片

普通读书笔记卡 · 5654.c.3.b.1

分层总工作还要乘层数

理解等级:中级

把规模n的问题等分成两个子问题、各层合计线性工作且层数为对数时,总工作为线性对数增长。关键是同时知道每层合计多少工作、分解进行了多少层。

不能只因有两次递归就判指数,也不能只因每次减半就判纯对数:两个子问题都继续处理,会保留整层的工作。原书此例每个子问题还有自己的线性循环,恰好展示了这项区别。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      二叉树的每一层的操作总数都为 ,树共有 log 间复杂度为 log 。 +1 层,因此时 第2 章 复杂度分析 hello‑algo.com 39 图2‑13 线性对数阶的时间复杂度 主流排序算法的时间复杂度通常为 lo

    参考来源

    - 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[30666,30776)) - 结论依据:实际linearLogRecur及已读图2-13给出每层n、对数层的结构,避免泛化全部分治。 - 原始内容:二叉树的每一层的操作总数都为 ,树共有 log 间复杂度为 log 。 +1 层,因此时 第2 章 复杂度分析 hello‑algo.com 39 图2‑13 线性对数阶的时间复杂度 主流排序算法的时间复杂度通常为 lo