基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

admin2019-08-15 58

问题基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

选项 A、O(nlog₂n)
B、O(log₂n)
C、O(n)
D、O(n²)

答案A

解析此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行log₂(n!)次比较。
由Stirling公式可知，log≈(n!)≈nlog₂n一1．44n+O(log₂n)，所以基于关键字比较的分类时间的下界是D(nlog≈n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。

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

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

计算机408

学硕统考专业

相关试题推荐

如下图所示为一个网络连接的示意图，主机1到主机2采用了SLIP网络连接，SLIP网络可以传输的最大数据段是296字节，主机2和主机3使用了以太网连接。请问：(1)为了使IP不分片，主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列
编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所
序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。
设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。
判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是()。
在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。
假设计算机系统采用CSCAN(循环扫描)磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。如果将磁盘替换为随机访问的Flash半导体存储器(如u盘、SSD等)，是否有比CSCAN更高效的磁盘调度策略?若有，给出磁盘调度策略的名称并说明

随机试题

我国台湾学者吴琼恩认为，个人决策在面临封闭的、可计划的、可计算的情境时，最佳决策路径是()
女性，35岁，间断胸闷不适2年，时有黑矇现象，近一周黑朦发作频繁，伴晕厥一次来诊。如果心电图示QT间期0．86s，T波宽大，U波明显，诊断为长QT间期综合征，推测其晕厥原因为
构成肾脏内髓部渗透压梯度的主要溶质是
王某擅自使用机动渔船渡客。渔船行驶过程中，被某港航监督站的执法人员发现，当场对王某作出罚款50元的行政处罚，并立即收缴了该罚款。关于缴纳罚款，下列哪一做法是正确的?
用人单位与职工终止或者解除劳动关系后，应当于()日内到当地公共就业服务机构办理登记手续。
()维护国家主权和安全，对进出我国国(边)境的外国人(包括无国籍人)和我国公民进行管理。
请用“洪水”“汽油”“神十”“小偷”这几个词语编一个故事。
下列选项中关于诉讼时效的说法正确的是()
A、She’llgetthethingsthemanneeds.B、Sallywantstogotothebookstoretoo.C、Thereisn’tenoughtimetogotothebookstor
The【S1】_____employer-basedhealth-insurancesystemexacerbates(加剧)concernsforwomenwhoareconsideringhavingachild.Ifawo

最新回复(0)

基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

计算机408

学硕统考专业

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

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。

判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是()。

在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

我国台湾学者吴琼恩认为，个人决策在面临封闭的、可计划的、可计算的情境时，最佳决策路径是()

女性，35岁，间断胸闷不适2年，时有黑矇现象，近一周黑朦发作频繁，伴晕厥一次来诊。如果心电图示QT间期0．86s，T波宽大，U波明显，诊断为长QT间期综合征，推测其晕厥原因为

构成肾脏内髓部渗透压梯度的主要溶质是

王某擅自使用机动渔船渡客。渔船行驶过程中，被某港航监督站的执法人员发现，当场对王某作出罚款50元的行政处罚，并立即收缴了该罚款。关于缴纳罚款，下列哪一做法是正确的?

用人单位与职工终止或者解除劳动关系后，应当于()日内到当地公共就业服务机构办理登记手续。

()维护国家主权和安全，对进出我国国(边)境的外国人(包括无国籍人)和我国公民进行管理。

请用“洪水”“汽油”“神十”“小偷”这几个词语编一个故事。

下列选项中关于诉讼时效的说法正确的是()

A、She’llgetthethingsthemanneeds.B、Sallywantstogotothebookstoretoo.C、Thereisn’tenoughtimetogotothebookstor

The【S1】_____employer-basedhealth-insurancesystemexacerbates(加剧)concernsforwomenwhoareconsideringhavingachild.Ifawo