我正在研究排序算法,我坚持定理,证明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 回答
从排序算法构建决策树很容易 . 排序算法可以尝试的每个比较将可能的订单组划分为两组 . 当只剩下一个可能的订单时,排序算法结束 .
你真的把你可能的决定写成一个树(<,>)到(左,右) . 如果你把树拉到侧面,或者向上/向下 .
现在一般问题尚未解决 . 什么是最好的决策树? :-)
这是一个例子:
这个决策树有6片叶子,最多需要3个决定才能到达叶子 .
通常,您实际构建决策树的方式称为“排序算法” . 如果对所有可能的输入运行算法,则可以跟踪它如何决定交换元素并构建相应的决策树 .