知识卡片

普通读书笔记卡 · 3612.a.6

两层三元组改善枢轴

理解等级:高级

对互异元素(或以原下标打破同值),单层三元组求中位数只得O(n log n)上界;SELECT3再把组中位数分成三元子组,取子组中位数的中位数作枢轴。

额外一层筛选意在保证线性最坏时间;原书把证明留为问题,不能套用五元组的7n/10界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 9 章问题 9-6(`OEBPS/chapter009.xhtml`,文本字符 [38500, 42000))。 - 结论依据:原文明确区分单层三元组的上界和重复分组的枢轴策略,并给出 SELECT3 伪代码。 - 原始内容:But by repeating the groups-of-3 idea on the middle group of medians, we can pick a pivot that guarantees O ( n ) time.