知识卡片

普通读书笔记卡 · 5626.k.1.a

短边递归控制最坏栈深度

理解等级:中级

划分后只递归较短一侧,较长一侧在当前函数循环中继续。每次新增栈帧的区间最多是上一层一半,因此最坏调用深度可限制为对数。

这靠显式循环改写获得,不依赖Go自动尾调用优化。坏基准仍可能让循环持续处理n-1规模,所以时间最坏仍平方;空间优化与划分质量是两种不同改进。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      仅对较短的子数组进 行递归。由于较短子数组的长度不会超过 ,因此这种方法能确保递归深度不超过log ,从而将最差空 间复杂度优化至 log 。代码如下所示: // === File: quick_sort.go ===

    参考来源

    - 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[27870,27979)) - 结论依据:实际quickSortTailCall短侧递归/长侧left/right更新支持。 - 原始内容:仅对较短的子数组进 行递归。由于较短子数组的长度不会超过 ,因此这种方法能确保递归深度不超过log ,从而将最差空 间复杂度优化至 log 。代码如下所示: // === File: quick_sort.go ===