知识卡片
固定比例分区仍近线性对数
快排不必每次对半分区。
只要每层两侧始终按固定正比例分开,如 9:1,递归深度仍为 Θ(log n),每层总分区成本 O(n),故总时间 O(n log n)。
比例越偏只增大常数;真正危险的是比例随规模逼近 0:1。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第7章 快速排序 · 查看原书依据
In fact, any split of constant proportionality yields a recursion tree of depth Θ(lg n), where the cost at each level is O(n).
参考来源
- 位置:《算法导论(第4版)》第 7 章 7.1–7.3 节(`OEBPS/chapter007.xhtml`,文本字符 [10000, 15000);图 7.1–7.5)。
- 结论依据:7.2 节用 9:1 与 99:1 划分的递归树说明固定比例仍有 Θ(lg n) 深度、每层 O(n) 工作,因此总为 O(n lg n)。
- 原始内容:In fact, any split of constant proportionality yields a recursion tree of depth Θ(lg n ), where the cost at each level is O ( n ).