首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。
对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。
admin
2019-07-18
47
问题
对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。
选项
A、O(n)
B、O(n
2
)
C、O(log n)
D、O(nlog n)
答案
D
解析
在排序过程中，每次比较会有两种情况出现，若整个排序过程中至少需要t次 比较，则显然会有2’种情况，由于n个记录总共有n!种不同的排列，因而必须有n!种不同的比较路径，于是有：2
t
≥n!，即t≥log
2
(n!)。因为log
2
(n!)≈nlog
2
n，所以t≥nlog
2
n。
转载请注明原文地址:https://kaotiyun.com/show/5JCi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中书省取代尚书省参与决策的部分职权，使尚书台成为主要行政中枢，这一历史现象出现在（）。
在良渚遗址的考古中，挖掘出了距今约五千年的大规模古城遗址，可以用来说明良渚文化()
完整地表述电磁场理论的物理学家是()。
下列法律文件中，规定内阁对君主负责的是()。
在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是：仅当需要访问某页面时，如果它不在内存，把它调入内存。按照这个思路，将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理，也可以产生类似的算法，不妨
对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。
假定有一条通带为100kHz的信道，每路信号的带宽为3．2kHz，各路信号间的防护带宽为0．8kHz。若采用频分多路复用，那么最多可以同时传输()路信号。
计算机系统采用补码运算是为了()。
DNS作为一种分布式系统，所基于的模式是()。
随机试题
苏轼词的革新意义是什么？
设f(x)具有二阶连续导数，f′(2)=0，=—2，则一定成立的是()
再生力最强的细胞是
泻南补北法适用于
为加强土地地价管理工作，2008年6月，A省国土资源部门切实加大了工作力度，A省政府出台了《关于加强全省土地调控工作的通知》，进一步宏观调控地价水平，稳定发展土地估价市场，制订地价标准，规范土地估价人员和机构监督管理方式，监管土地估价行业。2008年9月，
根据《票据法》，下列关于各种票据行为的表述，不正确的是()。
纸张的()都会影响印刷品颜色的鲜艳程度。
国内的培训机构联合发起自律公约，说明行业已深刻认识到当前教育培训市场面临的严重问题。虽然校外培训机构在不断发展，但扩张过快必然存在办学不规范、行业指导和行业规范相对滞后等现象。各种乱象大行其道，相关政策以及监管的缺位，也让培训机构有机可乘。因此倡导行业自律
设A～B，求a，b；
Inthatmythicalera【B1】______childrenwereseenandnotheard,anddid【B2】______theyweretoldwithout【B3】______,everyoneknew
最新回复
(
0
)
