对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为(62)；若采用快速排序算法，则时间和空间复杂度分别为(63)。 (63)

admin2019-07-12 52

问题对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为(62)；若采用快速排序算法，则时间和空间复杂度分别为(63)。
(63)

选项 A、O(n²)和O(n)
B、O(nlgn)和0(n)
C、O(n²)和O(1)
D、O(nlgn)和O(1)

答案C

解析本题考查算法分析的基础知识。排序和查找是基本的计算问题，存在很多相关的算法，不同的算法适用于不同的场合。不同的数据输入特点相同的算法也有不同的计算时间。若数据基本有序，对插入排序算法而言，则可以在近似线性时间内完成排序，即O(n)；而对于快速排序而已，则是其最坏情况，需要二次时间才能完成排序，即O(nz)。两个算法在排序时仅需要一个额外的存储空间，即空间复杂度均为常数时间复杂度O(1)。

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为(62)；若采用快速排序算法，则时间和空间复杂度分别为(63)。 (63)

软件设计师上午基础知识考试

软考中级

阅读以下说明和Java代码，将应填入(n)处。[说明]在一公文处理系统中，开发者定义了一个公文类OfficeDoc，其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时，关注此OfficeDoc类对象的相应的DocExplo

如果将数据库服务器(记为DB)作为一个外部实体，那么在绘制该系统的数据流图时，还应有哪些外部实体和数据存储?根据数据流图的设计原则，阅读下图所示的数据流图，找出其中的错误之处。

阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明]计算下列源代码的McCabe环数，画出控制流程图并用罗马数字标出区域。readx，y，z；type=“scalene”；if(x==yorx==zo

阅读以下说明，回答问题1～2，将解答填入对应的解答栏内。[说明]某程序的功能是输入三个正整数作为边长，判断三条边构成的三角形是否等边、等腰或是一般三角形。

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]输入1个长整型，求各位数字的平方和。例如：输入-123，输出14。#include＜stdio.h＞voidmain(){intdigit

读下列说明和Java代码，将应填入(n)处的字句写在对应栏内。【说明】已知某类库开发商捉供了一套类库，类库中定义了Application类和Document类，它们之间的关系如下图所示，其中，Application类表示应用程序自身，而Docu

“季裂”即黄铜零件在季节变化时出现裂纹的现象。()

追求个人特有潜能的充分发挥，理想和人的价值的完美实现属于()

A．硫糖铝B．雷尼替丁C．奥美拉唑D．西沙必利E．非甾体抗炎药可破坏胃黏膜屏障的药物是

依据《行政处罚法》的规定，罚款、没收违法所得或没收非法财物拍卖的款项，必须全部()。

Therearesomestandardformsoftimecharterpartyusedinthetimecharteringbusiness.ThetwomajorformsareNYPEandBAREC

使用调整现金流量法计算投资项目净现值时，折现率应选用()。

运输是修筑长城施工中的重要问题，当时搬运建材上山的方法主要有()。

如果一个工人可管理多个设备，而一个设备只被一个工人管理，则实体“工人”与实体“设备”之间存在【】的联系。

In1788,AustraliawassettledbytheBritishasacolonyfounded