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

admin2019-01-16 80

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

选项

答案假定待排序的记录有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/viRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

巴黎和会召开的时间是()。

印加人记载事物使用的方法是()。

冶铁技术中的淬火法提高了铁器的坚韧与锋利程度，这一技术最早出现在()。

商代青铜器的制作技术很高，尤其是礼器的制作，造型美观，纹饰精巧，是水平极高的工艺品，其中主流的花纹是()。

两宋时期，不同地域曾出现濂、洛、关、阐等学术流派。北宋后期到南宋中期，王安石的新学成为影响最大的学派，这主要是由于()

到1869年为止，人类已发现了多少种化学元素()。

提出电磁感应定律的是物理学家()。

同步发电机失磁时，功率因数表示进相。()

下列属于泰勒评价理念特点的是()

A．染色单体型畸变B．染色体型畸变C．基因突变D．染色体畸变E．染色体数目改变通过光学显微镜观察不到，需结合生长发育、生化和形态等表型改变来判断的是

"物极必反"说明了阴阳的何种关系

某女性患者，38岁。牙龈自发性出血1年半就诊。检查：舌缘、两颊黏膜多处瘀斑，患者自述平时轻微碰撞皮肤即会出现瘀斑。血常规检查：血小板计数30×109／L。下列哪种措施也可用于治疗该病()

患儿，女，6岁。左侧颈旁肿痛结块3天。皮色未变，肿核形如鸽卵大。活动度不大。外治应首选

在机器设备质量综合评价中，对其电气设备应检查哪些方面?

根据以下资料，回答91-95题。上表中2001年的医院人院人数比1995年增长了()。

请简述共情与理解、同情的区别。

AuniquelaboratoryattheUniversityofChicagoisbusyonlyatnight.Itisadream【C1】______whereresearchersareatworkstu