知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.2.a.13 · 生成模型:未记录

最坏线性选择需要可靠分割

理解等级:中级

标准中位数的中位数选择将元素分成五个一组,选各组中位数,再递归求这些中位数的中位数作为枢轴。互异键下,足够多元素位于枢轴两侧,可得到 T(n)≤T(⌈n/5⌉)+T(7n/10+O(1))+O(n),因此最坏线性。含重复键时需采用能排除整个等值区间的分区等措施,才能保留相应保证。

书中改用四元组并声称最坏线性;即使按正文声称的分界,直接递推也只有 T(n/4)+T(3n/4)+O(n),不能由此证明线性。图中代码递归取多层组中值,与精确选出所有组中值的中位数也不是同一过程,因此不能直接套用正文的分界证明。书中时间表只说明特定机器、输入和实现的观察,不能证明渐近上界。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      BFPRT(Blum-Floyd-Pratt-Rivest-Tarjan)算法(Blum等,1973),其性能见表4-2的最后一列。在统一生成的随机化数据上执行10次试验,最好和最坏的结果都被舍弃。表4-3给出了使用不同的切分子数组方法的中值排序的性能。平均情况下,使用随机中枢选择算法的计算趋势线(

    参考来源

    - 位置:《算法技术手册》第4章《分析》(spine1506;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1469.html;u078-ch04-014)。 - 结论依据:78全文、03200–03205性能表及完整代码实读;标准五元分组和递推为分析推导,未运行代码。 - 原始内容:BFPRT(Blum-Floyd-Pratt-Rivest-Tarjan)算法(Blum等,1973),其性能见表4-2的最后一列。在统一生成的随机化数据上执行10次试验,最好和最坏的结果都被舍弃。表4-3给出了使用不同的切分子数组方法的中值排序的性能。平均情况下,使用随机中枢选择算法的计算趋势线(