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

admin2019-07-12 25

问题对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)

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

软考中级

请用120字以内文字，从业务的继承性、升级成本(时间、工作量)和扩展性三个方面简要说明开发人员所提方案的优点。WebService的三个基本技术是WSDL、SOAP、UDDI，它们都是以XML为基础定义的。请用120字以内文字，简要说明WSDL、SO

下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。A：待排序数组p，r:数组元素下标，从p到rq:划分的位置x：枢轴元素i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴

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

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

目前认为，肺心病的首要死亡原因是

患者，女，34岁。3周前腰腿疼痛，近5天明显，尤其遇寒冷天气则疼痛加重，饮食尚可，二便正常，舌淡苔白，脉沉迟。最佳选药是

以下关于行政诉讼第三人的说法中，哪些是正确的?

名义利率、通货膨胀率、实际利率三者之间的关系正确的是()。

Hundredsofyearsago,aRomanarmycamenorthfromEnglandtomakewaronScotland.TheScots,abravepeople,lovedtheircoun

用0、l、2、3、4五个数组成一个五位数，数字可以重复，问至少有三个连续的1的数有多少个?()

设f(x)连续，且f’(0)＞0，则存在δ＞0，使得()．

A.haveratifieditB.approvingitC.implementitsprovisionsD.restrictsmokinginpublicplacesE.causedbytobaccouseF.

Foxesandfarmershavenevergotonwell.Thesesmalldog-likeanimalshavelongbeenaccusedofkillingfarmanimals.Theyare

A、Totellcampuspersonnelofthenewlibraryservices.B、Toannouncethenewmoviesoncampusthissummer.C、Tonotifyuniversi