知识卡片
快排性能依赖划分质量
每轮近乎均分时,递归层数对数、每层合计线性,平均可得到nlogn;总选到极端基准时,每轮只少一个,退化为平方工作和线性递归深度。
首元素基准会被有序、逆序或某些重复数据触发退化,不能说最坏天然很罕见。随机或三数取中可改善常见输入,却不保证最坏消失;缓存和常数优势也依规模与实现,不能声称所有子数组都装得进缓存。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
每轮哨兵划分操作都将长度为 的数组划分为 长度为 和 的两个子数组,此时递归层数达到 ,每层中的循环数为 ,总体使用 时间。 ‧ 空间复杂度为 、原地排序:在输入数组完全倒序的情况下,达到最差递归深度 ,使用 栈 帧空间
参考来源
- 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[25743,25853))
- 结论依据:实际最坏分割/有序反例/基准优化,限定概率与性能。
- 原始内容:每轮哨兵划分操作都将长度为 的数组划分为 长度为 和 的两个子数组,此时递归层数达到 ,每层中的循环数为 ,总体使用 时间。 ‧ 空间复杂度为 、原地排序:在输入数组完全倒序的情况下,达到最差递归深度 ,使用 栈 帧空间