知识卡片
循环外形不决定整体复杂度
一层循环是否线性取决于迭代次数与每次工作;两层循环要分别看界限及内部调用。每轮将搜索范围减半可得对数步数,但遍历整棵二叉树并不因此只访问对数个节点。分治还需分析子问题规模与合并成本,不能仅凭出现递归或“两半”就断定总成本为n·log(n)。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 39 算法速度 · 查看原书依据
每当编写任何包含循环或递归调用的东西时,我们都会下意识地检查运行时间和内存需求。很多时候这并不是一个正式的过程,我们往往只是想快速确认一下,所做的事情在这种情况下是否合理。然而,我们有时会发现自己正在进行更详细的分析。这
参考来源
- 位置:《程序员修炼之道:通向务实的最高境界(第2版)》,`extracted/程序员修炼之道:通向务实的最高境界(第2版)/_epub-src/text/part0016_split_003.html`。
- 结论依据:本处实际展开的论点与例证;正文中的读者边界分析不冒充原书已提供的实现。
- 原始内容:每当编写任何包含循环或递归调用的东西时,我们都会下意识地检查运行时间和内存需求。很多时候这并不是一个正式的过程,我们往往只是想快速确认一下,所做的事情在这种情况下是否合理。然而,我们有时会发现自己正在进行更详细的分析。这