首页 文章

最坏情况最小排序时间复杂性定理

提问于
浏览
0

我正在研究排序算法,我坚持定理,证明n矢量上的排序算法至少在最坏的情况下具有时间复杂度

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

证明使用引理,该引理声明具有k个叶子的二叉树具有至少为天花板的高度(log2(n)) . 该定理表明你可以用n构建一个二元决策树!叶子并使用斯特林公式得到结果!它应该是排序算法领域的经典定理 .

我的问题是我无法弄清楚n是怎么回事!叶二叉树正在构建!例如,如果我们想要按递增顺序对向量v =(4,3,1)进行排序,我如何构建具有3!= 6个叶子的决策树?

我为可能的错误和不正确使用数学公式道歉 .

在此先感谢大家!

2 回答

  • 1

    从排序算法构建决策树很容易 . 排序算法可以尝试的每个比较将可能的订单组划分为两组 . 当只剩下一个可能的订单时,排序算法结束 .

    你真的把你可能的决定写成一个树(<,>)到(左,右) . 如果你把树拉到侧面,或者向上/向下 .

    a<b?
               |
         Y-----------N
         |           |
        b<c?        a<c?
         |           |
      Y-----N     Y-----N
      |     |     |     |
    (abc)  a<c? (bac)  b<c?
            |           |
         Y-----N     Y-----N
         |     |     |     |
       (acb) (cab) (bca) (cba)
    

    现在一般问题尚未解决 . 什么是最好的决策树? :-)

  • 2

    这是一个例子:

    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个决定才能到达叶子 .

    通常,您实际构建决策树的方式称为“排序算法” . 如果对所有可能的输入运行算法,则可以跟踪它如何决定交换元素并构建相应的决策树 .

相关问题