知识卡片
短边递归控制最坏栈深度
划分后只递归较短一侧,较长一侧在当前函数循环中继续。每次新增栈帧的区间最多是上一层一半,因此最坏调用深度可限制为对数。
这靠显式循环改写获得,不依赖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 ===