首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
对快速排序来讲,其最好情况下的时间复杂度是_______,其最坏情况下的时间复杂度是________。
对快速排序来讲,其最好情况下的时间复杂度是_______,其最坏情况下的时间复杂度是________。
admin
2014-12-25
43
问题
对快速排序来讲,其最好情况下的时间复杂度是_______,其最坏情况下的时间复杂度是________。
选项
答案
O(nlog
2
n) O(n
2
)
解析
快速排序的基本思想是由选取的中间元素把整个待排序空间分成左、右两个区域,其中左边区域中元素的关键字都不大于中间元素的关键字,而右边区域中元素的关键字都不小于中间元素的关键字,接下来再按上述思路继续对各个区域进行划分。最好情况下,每次选定的中间元素正好将待排序空间分成几乎等长的两个区域,这样仅需log
2
n趟划分即可。每趟划分所需时间复杂度为O(n),最好情况下的时间复杂度是O(nlog
2
n)。
最坏情况下,每次选取的中间元素不是最大就是最小,因此划分出的两个区域一个为空,而另一个仅比原空间少一个元素,故需要n一1趟划分。每趟划分的时间复杂度为O(n),因此,最坏情况下的时间复杂度为O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/2iVx777K
本试题收录于:
数据结构导论题库理工类分类
0
数据结构导论
理工类
相关试题推荐
一系统在扰动作用下的误差函数为EN(s)=,则系统由扰动引起的稳态误差essN等于【】
采用非屏蔽双绞线UTP将站点连接到集线器上,一段双绞线的最大长度为【】
在曼彻斯特编码中,每个比特持续时间的中间要进行电平跳变,从高电平跳变到低电平表示________。
NetWare网络操作系统大部分安装于服务器上,这部分称为_____,负责管理网络。
_____表示在单位时间内通过某个网络(或信道、接口)的数据量。
面向对象程序设计(OOP)的两个阶段是______设计和_______设计。
作为系统开发的后期阶段,系统实施的目的是把审核过的_______说明书转换为可以实际运行的系统。
在题39图所示的系统中,要求按钮未按之前为全暗,每按一次,则发光二极管LED亮其中一个,并从LED0→LED1…LED7→逐个循环点亮。已知8255A各端I:1地址为60H~63H。请根据注解要求完成未完成的程序指令,要求一条横线一条指令。(控制字中无关
箭线式网络图以箭线代表______,以结点代表______。
设P为指向双向循环链表中某个结点的指针,p所指向的结点的两个链域分别用p→llink和p→rlink表示,则同样表示P指针所指向结点的表达式是______
随机试题
C语言中,若inta[5],i,*p=a;,则与&a[i]等价的指针表示是_________。
下列属于需求分析阶段工作的是()
一患者突发右侧胸痛,并伴呼吸困难就诊。查体:气管向左侧移位、右侧胸壁隆起,呼吸运动和触觉语颤减弱,叩诊呈鼓音,听诊呼吸音消失。疑为气胸其X线表现应为
在药物临床应用管理中不属于临床药学专业技术人员工作任务的是
某企业2007年12月31日购入一台设备,入账价值为200万元,预计使用寿命为10年,预计净残值为20万元。采用年限平均法计提折旧。2008年12月31日该设备存在减值迹象,经测试预计可收回金额为120万元。2008年12月31日该设备账面价值应为(
社会政策评估是应用性的研究活动,注重对( )及其结果的分析、阐释和预测。
新课程倡导的评价主体多元化是指()
InAmericaalone,tippingisnowa$16billion-a-yearindustry.Arecentpollshowedthat40%ofAmericans【C1】______thepractice
A、Hedidn’tknowwhatwouldhappenifhemadethesuggestion.B、Hedidn’tfeelnervousafterhehadputforwardthesuggestion.
A、Trytoretainasmanynewwordsaspossible.B、Practicewordsatappropriateintervals.C、Learndifficultwordswiththehighe
最新回复
(
0
)