利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。

admin2019-01-16 58

问题利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。

选项

答案假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是h，则叶子结点个数最多为2^h-1；反之，若有u个叶子结点，则二叉树的高度至少为(log₂u)+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log₂(n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log₂(n!)。根据斯特林公式，有log₂(n!)=O(nlog₂n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为O(nlog₂n)。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/glRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。

计算机408

学硕统考专业

建立帝国财政收支总账和元首金库，直接控制和调节全国财政收支的是()。

下列关于罗马共和国政治制度的叙述，不正确的是()。

下列哪个文件标志着“文化大革命”的发起?()

秦统一过程中，最先和最后灭掉的国家是()。

下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

不是黏膜下肌瘤的临床表现的是()

A．Kmax值不变，Vmax降低B．Km值降低，Vmax不变C．Km值增高，Vmax不变D．Km值降低，Vmax降低酶非竞争性抑制的特点是

慢性肺心病，应用抗凝冶疗，错误的是

商用房地产抵押贷款是开发商以销售的房地产作为抵押担保向金融机构申请的贷款。()

基金管理人应当自募集期限届满之日起()日内聘请法定验资机构验资，自收到验资报告之日起()日内，向中国证监会提交验资报告，办理基金备案手续，并予以公告。

(2010年)下列税率形式，应用于土地增值税的是()。

“随心还”和“气球贷”属于()还款方式。

(2011年考试真题)根据营业税法律制度的规定，下列项目中，不免征营业税的是()。