最好情况下的算法时间复杂度为O(n)的是( )。

admin2021-08-17 39

问题最好情况下的算法时间复杂度为O(n)的是( )。

选项 A、插入排序
B、归并排序
C、快速排序
D、堆排序

答案A

解析直接插入排序在最好情况下，即待排序列已按关键码有序，每趟操作只需1次比较，不需移动。总比较次数＝n－1次。所以时间复杂度为O(n)。
归并排序和堆排序在平均情况和最好情况下的时间复杂度为O(nlogn)。
快速排序在平均情况下的时间复杂度为O(nlogn)，最坏情况下的时间复杂度为O(n²。)。

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

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。　　(1)关键字自小到大有序(key1＜key2＜……＜keyn)；　　(2)关键字自大到小逆序(
如果一个没有内存映射的IO设备与主存之间交换数据，希望这种数据交换不经过CPU来完成，那么，可以采用的方法是()。
有一结点的关键字序列F={129，72，180，105，147，96，45，69}，散列函数为H(k)=kmod11，其中k为关键字，散列地址空间为0～10。要求：试按各关键字在序列F中的次序将它们依次插入一棵初始为空的平衡二叉排序树中，画出每一步插入
一台模型机共有7条指令，主频25MHz，各指令的使用频率与CPI如表2-4所示。该模型机有8位和16位两种指令字长，采用2-4扩展操作码。8位字长指令为寄存器-寄存器(R-R)二地址类型，16位字长指令为寄存器-存储器(R—M)二地址变址寻址类型(-128
有一个文件系统如图7—2所示。其中的方框表示目录，椭圆圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址(各占2B，共4B)。若下级文件是目录文件，指示其第一个磁盘块地址。若
通过对方格中每个点设置相应的CMYK值就可以将方格涂上相应的颜色。以下3个程序段都可实现对一个8×8的方格涂上黄色的功能。假设Cache的数据区大小为512B，采用直接映射，块大小为32B，存储器按字节编址，sizeof(int)=4
设一个一维整数数组中有n(n＞1)个元素，设计一个在时间和空间两方面尽可能高效的算法，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求：说明你所设计算法的时间复杂度和空间复杂度。
已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。IEEE754标准短实数。【注】题中机器数中间加空格是为了读写方便，并非机器数的一部分，答题时如有需要可类似表示。
下列有关I／O编址方式的描述中，正确的是()。

随机试题

房屋租金中的商品租金是由成本租金加上保险费、地租和()等八项因素组成。
下列有关风湿病的描述，错误的是
心电图示右心室肥大，最有可能的先天性心脏病是（）。
(2004}通用实验室标准单元的开间是由实验台的宽度、布置方式及间距决定的，实验台平行布置的标准单元，其开间不宜小于下列哪项?
出现金融自由化最直接的原因是()。
强调学习在于在头脑中构造和组织一种完形是()学习理论。
牙本质过敏与下列哪些结构没有关系()。
请在“答题”菜单下选择“字处理”命令，然后按照题目要求再打开相应的命令，完成下面的内容，具体要求如下：设置页面“纸型”为“16开(18.4x26厘米)”。
In1784,fiveyearsbeforehebecamepresidentoftheUnitedStates,GeorgeWashington,52,wasnearlytoothless.Sohehireda
Ascitizensofadvancedbutvulnerableeconomies,wemusteitherrelentlesslyincreasethequalityofourskillsorseeourstan

最新回复(0)

最好情况下的算法时间复杂度为O(n)的是( )。

计算机408

学硕统考专业

已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。 (1)关键字自小到大有序(key1＜key2＜……＜keyn)； (2)关键字自大到小逆序(

如果一个没有内存映射的IO设备与主存之间交换数据，希望这种数据交换不经过CPU来完成，那么，可以采用的方法是()。

有一结点的关键字序列F={129，72，180，105，147，96，45，69}，散列函数为H(k)=kmod11，其中k为关键字，散列地址空间为0～10。要求：试按各关键字在序列F中的次序将它们依次插入一棵初始为空的平衡二叉排序树中，画出每一步插入

通过对方格中每个点设置相应的CMYK值就可以将方格涂上相应的颜色。以下3个程序段都可实现对一个8×8的方格涂上黄色的功能。假设Cache的数据区大小为512B，采用直接映射，块大小为32B，存储器按字节编址，sizeof(int)=4

设一个一维整数数组中有n(n＞1)个元素，设计一个在时间和空间两方面尽可能高效的算法，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求：说明你所设计算法的时间复杂度和空间复杂度。

已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。IEEE754标准短实数。【注】题中机器数中间加空格是为了读写方便，并非机器数的一部分，答题时如有需要可类似表示。

下列有关I／O编址方式的描述中，正确的是()。

房屋租金中的商品租金是由成本租金加上保险费、地租和()等八项因素组成。

下列有关风湿病的描述，错误的是

心电图示右心室肥大，最有可能的先天性心脏病是（）。

(2004}通用实验室标准单元的开间是由实验台的宽度、布置方式及间距决定的，实验台平行布置的标准单元，其开间不宜小于下列哪项?

出现金融自由化最直接的原因是()。

强调学习在于在头脑中构造和组织一种完形是()学习理论。

牙本质过敏与下列哪些结构没有关系()。

请在“答题”菜单下选择“字处理”命令，然后按照题目要求再打开相应的命令，完成下面的内容，具体要求如下：设置页面“纸型”为“16开(18.4x26厘米)”。

In1784,fiveyearsbeforehebecamepresidentoftheUnitedStates,GeorgeWashington,52,wasnearlytoothless.Sohehireda

Ascitizensofadvancedbutvulnerableeconomies,wemusteitherrelentlesslyincreasethequalityofourskillsorseeourstan