对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

admin2012-06-26 82

问题对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

选项 A、O(n)
B、O(n²)
C、O(logn)
D、O(nlogn)

答案D

解析在排序过程中，每次比较会有两种情况出现，若整个排序过程中至少需要t次比较，则显然会有2^t种情况，由于n个记录总共有n!种不同的排列，因而必须有n!种不同的比较路径，于是有：2^t≥n!，即t≥log₂(n!)。因为log₂(n!)≈nlog₂n，所以t≥nlog₂n。

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

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

计算机408

学硕统考专业

相关试题推荐

西汉诸侯国的政权机构和中央基本上相同，其中需要中央直接任命的有()
下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在
1854年，英国外交大臣致函英国驻华公使说：“为了适应外商对农业产品已增加了的需要，新的贸易市场尚待开辟。”1856年，法国外长则指令法国驻华代办强调“商业关系的推广”，并强调“这是一个关系到至高无上权益的问题”。这说明()。
下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界
某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制，则在链式查询、计数器定时查询和独立请求三种方式下，
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

随机试题

左心衰竭肺循环淤血的主要临床表现，下列哪项不正确
A．呕吐清水痰涎B．呕吐黏痰黄水C．呕吐物酸臭D．呕吐脓汁实热证则表现为
小柴胡汤的组成有
髓内肿瘤的特点不包括
下列说法错误的是
男性，4岁，诉发音不清求治，口腔检查：舌不能自由前伸．伸舌时舌尖部呈“M”形．智力发育正常．引起发音不清可能的原因是
产钳助娩必须具备的条件中，下列哪项不完全正确
计算机的运算精度通常取决于()。
下列津贴、补贴中不应当计入员工工资、薪金所得项目计征个人所得税的有()。
西周在王位继承上实行()。

最新回复(0)

对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

计算机408

学硕统考专业

西汉诸侯国的政权机构和中央基本上相同，其中需要中央直接任命的有()

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界

古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

左心衰竭肺循环淤血的主要临床表现，下列哪项不正确

A．呕吐清水痰涎B．呕吐黏痰黄水C．呕吐物酸臭D．呕吐脓汁实热证则表现为

小柴胡汤的组成有

髓内肿瘤的特点不包括

下列说法错误的是

男性，4岁，诉发音不清求治，口腔检查：舌不能自由前伸．伸舌时舌尖部呈“M”形．智力发育正常．引起发音不清可能的原因是

产钳助娩必须具备的条件中，下列哪项不完全正确

计算机的运算精度通常取决于()。

下列津贴、补贴中不应当计入员工工资、薪金所得项目计征个人所得税的有()。

西周在王位继承上实行()。