时间戳

首页 > 解决方案 > 最坏情况最小排序时间复杂度定理

algorithm - 最坏情况最小排序时间复杂度定理

问题描述

我正在研究排序算法，我被困在证明一个 n 向量上的排序算法至少在最坏情况下的时间复杂度为

n*log2(n) + (1/2)*log2(n) - log2(e)*n + O(1)

您的证明使用了一个引理，该引理指出具有 k 个叶子的二叉树的高度至少为上限 (log2(n))。该定理指出，您可以用 n! 构建二叉决策树！叶并使用斯特林公式得到结果！应该是排序算法领域的经典定理。

我的问题是我无法弄清楚 n! 叶二叉树已构建！例如，如果我们想按升序对向量 v=(4,3,1) 进行排序，我该如何构建具有 3!=6 个叶子的决策树？

对于可能的错误和没有正确使用数学公式，我深表歉意。

在此先感谢大家！

标签： algorithmsortingtime-complexity

解决方案

这是一个例子：

if (v[0] <= v[1]) {
  if (v[1] <= v[2]) {
    // Sorted order: v[0], v[1], v[2]
  } else {
    // v[1] > v[2], so v[1] is a maximal element
    if (v[0] <= v[2]) {
      // Sorted order: v[0], v[2], v[1]
    } else {
      // Sorted order: v[2], v[0], v[1]
    }
  }
} else {
  // v[0] > v[1]
  if (v[1] > v[2]) {
    // Sorted order: v[2], v[1], v[0]
  } else {
    // v[1] <= v[2], so v[1] is a minimal element
    if (v[0] <= v[2]) {
      // Sorted order: v[1], v[0], v[2]
    } else {
      // Sorted order: v[1], v[2], v[0]
    }
  }
}

这棵决策树有 6 个叶子，最多需要 3 个决策才能到达叶子。

通常，您实际构建决策树的方式称为“排序算法”。如果您在所有可能的输入上运行算法，您可以跟踪它如何做出关于交换元素的决策并构建相应的决策树。

推荐阅读