知识卡片

普通读书笔记卡 · 3615.c

固定比例分区仍近线性对数

理解等级:中级

快排不必每次对半分区。

只要每层两侧始终按固定正比例分开,如 9:1,递归深度仍为 Θ(log n),每层总分区成本 O(n),故总时间 O(n log n)。

比例越偏只增大常数;真正危险的是比例随规模逼近 0:1。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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 ).