Lec7 Sorting(4)

接下来登场的是决策树。😎

排序问题的下界

  • 排序问题的时间复杂度下界为 Ω(N)，上界为 O(N log N)。
  • 任何排序算法在最坏情况下不能少于 Ω(N) 时间。即使是最优的排序算法，其时间复杂度也不会低于 Ω(N)。
  • 当前已知的最优排序算法，其时间复杂度为 O(N log N)，适用于平均情况和最坏情况。
  • 这是计算机科学中最重要、最有用的证明之一：任何基于键值比较的排序算法，在最坏情况下，其时间复杂度不可能低于 Ω(N log N)。

解释：

  1. Ω(N)（下界）：
    这表示无论使用什么排序算法，在最坏的情况下，至少需要进行 N 次操作（比如在比较排序中，至少需要检查每个元素一次）。因此，排序问题的下界是 Ω(N)。

  2. O(N log N)（上界）：
    当前最优秀的已知排序算法（如归并排序、堆排序、快速排序）的时间复杂度是 O(N log N)，这是排序问题的上界。对于平均和最坏情况，这些算法已经达到最优性能。

  3. 基于比较的排序算法：
    基于键值比较的排序算法（如快速排序、归并排序、堆排序）在最坏情况下，其时间复杂度无法超过 O(N log N)，也不能少于 Ω(N log N)。这意味着这些算法的时间复杂度在最坏情况下是有下界的，不可能更快。

决策树（Decision Tree）

  • 假设所有的 N 个元素是不同的
    假设要排序的所有元素都不相同，确保每个元素都有唯一的值。

  • 任何基于比较的排序算法都可以通过决策树来建模
    决策树是一种二叉树，能够表示任何做出二元决策的算法。每次决策（比较）都对应树中的一个节点，决策的结果通过树的分支来表示。

  • 二元决策：是或否；小于或大于
    每个决策的结果只有两种可能：例如 "是否小于某个值" 或 "是否大于某个值"。

  • 每次决策通过树中的分支表示
    每一次比较后，决策树会通过分支继续往下，直到最终确定元素的正确顺序。

排序算法与决策树

  • 所有的排序算法都可以被视为一个“寻找”正确排列的过程，目标是找到排序后的输入列表。
  • 算法通过在决策树中做出比较，逐步缩小可能的排列，直到树的叶子节点（包含唯一排列的节点）被达到。

决策树的深度与算法性能

  • 决策树中最深的节点深度表示算法为了找到排序结果所需的最长决策序列。
  • 该深度决定了最坏情况时，排序所需的决策次数，即算法的最坏情况时间复杂度。
image-20241120131713747

二叉树的性质（Binary Tree Properties）

  • 深度为 d 的二叉树最多有 \(2^d\) 个叶子节点
    一棵深度为 \(d\) 的二叉树，其叶子节点的数量最多为 \(2^d\)。这是因为在每一层，节点数最多是前一层节点数的两倍。

  • **具有 L 个叶子的二叉树至少需要 $ _2 L $ 的深度**
    若一棵二叉树有 \(L\) 个叶子节点，则其深度至少为 $ _2 L $，即树的深度与叶子节点数量的对数成正比。

排序算法中的决策树

  • 使用比较的排序算法的最小深度
    对于任何仅使用比较的排序算法，排序 N 个元素的决策树必须有 \(N!\) 个叶子节点，因为每个叶子节点对应一种排列（即排序的最终结果）。为了表示这些排列，决策树的深度至少为 $ _2 (N!) $。

  • 比较次数的下界
    任何仅依赖于元素比较的排序算法，在最坏情况下至少需要进行 $ _2 (N!) $ 次比较。由于 \(N!\) 是 \(N\) 的阶乘，$ _2 (N!) $ 近似为 \(N \log N\)，因此，任何基于比较的排序算法的时间复杂度下界是 $ (N N) $。

选择问题（Selection Problems）

  • 选择问题的定义
    选择问题要求在一个包含 \(N\) 个元素的集合中：
    • 找出最小的元素
    • 找出两个最小的元素
    • 找出中位数
  • 比较基排序算法的下界
    这些选择问题可以通过决策树模型来确定其下界。假设所有元素都是唯一的，那么通过比较进行选择时，解决这些问题所需的最少比较次数可以通过决策树的深度来推导。

寻找第 \(k\) 小元素的下界

  • 寻找第 \(k\) 小元素的比较次数
    要找到第 \(k\) 小的元素，需要进行的最少比较次数为：
    $ N - k + _2 $ 其中，\(\binom{N}{k-1}\) 表示从 \(N\) 个元素中选择 \(k-1\) 个元素的组合数。

寻找最小元素的下界

  • 寻找最小元素的最少比较次数
    任何基于比较的算法，在最坏情况下，找到最小元素至少需要 \(N-1\) 次比较。因为对于 \(N\) 个元素，需要进行至少 \(N-1\) 次比较才能确定哪个元素是最小的。

决策树的性质

  • 决策树的深度与叶子节点数量
    如果决策树的所有叶子节点都在深度 \(d\) 或更深的层次，则该决策树必须有至少 \(2^d\) 个叶子节点。

  • 二叉树的性质
    决策树是二叉树，每个非叶子节点有两个子节点。对于深度为 \(d\) 的二叉树，其最多有 \(2^d\) 个叶子节点。

寻找最小元素的决策树

  • 最小元素的决策树
    寻找 \(N\) 个元素中的最小值的决策树必须至少有 \(2^{N-1}\) 个叶子节点。
    这是因为，在比较基算法中，每一次比较都会使得某个元素被排除在外，最终通过 \(N-1\) 次比较确定最小元素。

  • 最小元素的决策树的深度
    对于寻找最小元素的决策树，所有叶子节点的深度都至少为 \(N-1\)，即树的深度至少为 \(N-1\)，这是由于需要进行 \(N-1\) 次比较才能最终确定最小元素。