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

admin2019-07-12 54

问题对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://www.kaotiyun.com/show/1hCZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

根据以上说明设计的实体联系图如下图所示，请指出读者与图书、书目与读者、书目与图书之间的联系类型。请指出问题2中给出的读者、书目关系模式的主键，以及图书、借还记录和预约登记关系模式的主键和外键。

阅读以下说明以及Java程序。【说明】传输门是传输系统中的重要装置。传输门具有Open(打开)、Closed(关闭)、Opening(正在打开)、StayOpen(保持打开)和Closing(正在关闭)五种状态。触发状态的转换事件有click

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用连接存储结构进行存储，root指向根接点，p所指结点为任一给定的结点，编写一个求从根结点到p所指结点之间路径的函数。voidpath(root,p)

Languagebelongstoeachmemberofthesociety,tothecleaner______totheprofessor.

()不属于婴儿得水痘时的表现。

在原始凭证上书写阿拉伯数字，正确的是()。

在地役权法律关系中，下列表述正确的有()。

持续的规划程序的具体目标为()。

下列属于资产的是()。

不属于计划类的文种是()。

散列法存储中处理碰撞的方法主要有两类：【】和开地址法。

两个关系进行自然连接运算，必须具有()。

以下程序段中，与其他3个功能不同的程序段是()。