知识卡片

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

比较排序下界来自排列区分

理解等级:中级

对n个互异元素,比较排序必须区分n!种可能排列。二元比较决策树高度h最多容纳2^h个叶子,因此最坏比较次数至少ceil(log₂(n!)),增长为Ω(n log n)。03184展示四元素24种排列的决策树,最长路径需要5次比较。

原文把下界写成“至少O(n log n)”容易与上界符号混淆,应写Ω;又把树高误解释为存在一条最短路径的长度。平均情况的Ω(n log n)还需要指定如所有排列等概率的模型,不能仅凭最坏树高证明任意分布下的期望。计数、基数等使用额外键结构的算法不受纯比较模型下界的直接限制。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      决策树。决策树的叶子就相当于下面的一个排列,每个排列至少在树中与一个叶子相对应。每条路径从根到叶子上的节点就相当于一个比较序列。这棵树的高度就是从根到叶子的最长路径上的比较节点的数目,例如,图4-5中的树的高度就是5,因为在所有的情况下,五次比较是必需的(虽然在四种情况下只需要四次比较)。 图 4-

    参考来源

    - 位置:《算法技术手册》第4章《分析技术》(spine1495;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1458.html;u065-ch04-006)。 - 结论依据:65全文、03184四元素决策树及03185–03186取整符号图实读;叶数/树高推导明确比较模型。 - 原始内容:决策树。决策树的叶子就相当于下面的一个排列,每个排列至少在树中与一个叶子相对应。每条路径从根到叶子上的节点就相当于一个比较序列。这棵树的高度就是从根到叶子的最长路径上的比较节点的数目,例如,图4-5中的树的高度就是5,因为在所有的情况下,五次比较是必需的(虽然在四种情况下只需要四次比较)。 图 4-