知识卡片

普通读书笔记卡 · 1881.b.2

循环外形不决定整体复杂度

理解等级:中级

一层循环是否线性取决于迭代次数与每次工作;两层循环要分别看界限及内部调用。每轮将搜索范围减半可得对数步数,但遍历整棵二叉树并不因此只访问对数个节点。分治还需分析子问题规模与合并成本,不能仅凭出现递归或“两半”就断定总成本为n·log(n)。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 39 算法速度 · 查看原书依据

      每当编写任何包含循环或递归调用的东西时,我们都会下意识地检查运行时间和内存需求。很多时候这并不是一个正式的过程,我们往往只是想快速确认一下,所做的事情在这种情况下是否合理。然而,我们有时会发现自己正在进行更详细的分析。这

    参考来源

    - 位置:《程序员修炼之道:通向务实的最高境界(第2版)》,`extracted/程序员修炼之道:通向务实的最高境界(第2版)/_epub-src/text/part0016_split_003.html`。 - 结论依据:本处实际展开的论点与例证;正文中的读者边界分析不冒充原书已提供的实现。 - 原始内容:每当编写任何包含循环或递归调用的东西时,我们都会下意识地检查运行时间和内存需求。很多时候这并不是一个正式的过程,我们往往只是想快速确认一下,所做的事情在这种情况下是否合理。然而,我们有时会发现自己正在进行更详细的分析。这