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

admin2021-08-17 44

问题最好情况下的算法时间复杂度为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

学硕统考专业

相关试题推荐

某计算机采用虚拟页式存储技术，系统为每一个进程提供65536B的地址空间，页面大小为4096B，某一个进程的代码段有32768B，数据段16396B，堆栈段在进程创建时为1024B，运行中最大会增长到15284B。那么，对这个进程正确的描述是()。
如果一个没有内存映射的IO设备与主存之间交换数据，希望这种数据交换不经过CPU来完成，那么，可以采用的方法是()。
某文件系统空间的最大容量为4TB(1T=240)，以磁盘块为基本分配单位，磁盘块大小为lKB。文件控制块(FCB)包含一个512B的索引表区。请回答下列问题。假设索引表区采用如下结构：第0～7字节采用格式表示文件创建时预分配的连续存储空间，其中起始块
某16位计算机中，带符号整数用补码表示，数据Cache和指令cache分离。题44表给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，mem表示存储单元地址，(x)表示寄存器x或存储单元x的内容。该计算机采用5段流水方式执行指令，各流水段分别是取指(
假定某计算机的CPU主频为80MHz，CPI为4，并且平均每条指令访存1．5次，主存与cache之间交换的块大小为16B，Caehe的命中率为99％，存储器总线宽度为32位。请回答下列问题。该计算机的MIPS数是多少?平均每秒Cache缺失的次数是多少
假设某计算机按字编址，Cache有4个行，cache和主存之间交换的块大小为1个字、若Cache的内容初始为空，采用2路组相联映射方式和LRU替换算法，当访问的主存地址依次为0，4，8，2，0，6，8，6，4，8时，命中cache的次数足
假定编译器规定int和short类型长度分别为32位和16位，执行下列C语言语句：unsigtledshortx=65530：unsignedintv=x；得到y的机器数为
有一主存-Cache层次的存储器，其主存容量为1MB(按字节编址)，Cache容量为16KB，每字块有8个字，每字为32位，采用直接地址映像方式。若主存地址为35301H，且CPU访问Cache命中，则在Cache的第()号字块(Cache字块号从
有一个文件系统如图7—2所示。其中的方框表示目录，椭圆圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址(各占2B，共4B)。若下级文件是目录文件，指示其第一个磁盘块地址。若
通过对方格中每个点设置相应的CMYK值就可以将方格涂上相应的颜色。以下3个程序段都可实现对一个8×8的方格涂上黄色的功能。假设Cache的数据区大小为512B，采用直接映射，块大小为32B，存储器按字节编址，sizeof(int)=4

随机试题

在Word2010中，文本被剪切后，它被保存在()
汉字信息交换码________是我国颁布的国家标准。
关于传染病流行程度下列哪项是错误的
[1998年第109题]下列哪一项为允许人行道路红线的建筑突出物?
建筑电气工程中，母线槽的安装连接要求有()。
根据《税收征收管理法》的规定，以暴力、威胁方法拒不缴纳税款的，是骗税。()
甲公司以一批存货对乙公司进行股权投资，该批存货的成本为2000万元，公允价值为2500万元。若甲公司选择按所得税优惠政策最高年限处理，不考虑其他因素，此项业务影响甲公司当年应纳税所得额为()万元。
不属于旅游行政处罚的证据的是()
教师道德
关于诈骗罪，下列说法正确的是()。

最新回复(0)

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

计算机408

学硕统考专业

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

假定某计算机的CPU主频为80MHz，CPI为4，并且平均每条指令访存1．5次，主存与cache之间交换的块大小为16B，Caehe的命中率为99％，存储器总线宽度为32位。请回答下列问题。该计算机的MIPS数是多少?平均每秒Cache缺失的次数是多少

假设某计算机按字编址，Cache有4个行，cache和主存之间交换的块大小为1个字、若Cache的内容初始为空，采用2路组相联映射方式和LRU替换算法，当访问的主存地址依次为0，4，8，2，0，6，8，6，4，8时，命中cache的次数足

假定编译器规定int和short类型长度分别为32位和16位，执行下列C语言语句：unsigtledshortx=65530：unsignedintv=x；得到y的机器数为

有一主存-Cache层次的存储器，其主存容量为1MB(按字节编址)，Cache容量为16KB，每字块有8个字，每字为32位，采用直接地址映像方式。若主存地址为35301H，且CPU访问Cache命中，则在Cache的第()号字块(Cache字块号从

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

在Word2010中，文本被剪切后，它被保存在()

汉字信息交换码________是我国颁布的国家标准。

关于传染病流行程度下列哪项是错误的

[1998年第109题]下列哪一项为允许人行道路红线的建筑突出物?

建筑电气工程中，母线槽的安装连接要求有()。

根据《税收征收管理法》的规定，以暴力、威胁方法拒不缴纳税款的，是骗税。()

甲公司以一批存货对乙公司进行股权投资，该批存货的成本为2000万元，公允价值为2500万元。若甲公司选择按所得税优惠政策最高年限处理，不考虑其他因素，此项业务影响甲公司当年应纳税所得额为()万元。

不属于旅游行政处罚的证据的是()

教师道德

关于诈骗罪，下列说法正确的是()。