首页
登录
从业资格
对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下:统计A中-
对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下:统计A中-
题库
2022-08-02
19
问题
对n个元素值分别为-1、0或1的整型数组A进行升序排序的算法描述如下:统计A中-1、0和1的个数,设分别为n1、n2和n3,然后将A中的前n1个元素赋值为-1,第n1+1到nl+n2个元素赋值为0,最后n3个元素赋值为1。该算法的时间复杂度和空间复杂度分别为( )。
选项
答案
A
解析
时间复杂度是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作,以该操作重复执行的次数作为算法的时间度量。一般来说,算法中原操作重复执行的次数是规模n的某个函数T(n)。由于许多情况下要精确计算T(n)是困难的,因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。其定义如下:
如果存在两个常数c和m,对于所有的n,当n≥m时有f(n)≤cg(n),则有f(n)=O(g(n))。也就是说,随着n的增大,f(n)渐进地不大于g(n)。例如,一个程序的实际执行时间为T(n)=3n3+2n2+n,则T(n)=O(n3)。
在本题中,根据题目的描述,我们可以知道,遍历完整个数组中的元素,和修改数组中各元素的值都需要时间n,因此是2n,那么该算法的时间复杂度为O(n)。
空间复杂度是指程序运行从开始到结束所需的辅助存储量,在本题中,只需要辅助存储量来存储统计的元素个数,因此其空间复杂度为O(1)。
转载请注明原文地址:https://tihaiku.com/congyezige/2409965.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
已知有序数组a的前10000个元素是随机整数,现需查找某个整数是否在该数组中。以
某超市销售系统的部分关系模式如下 商品表:Commodity(Ccode,
某汽车租赁公司建立汽车租赁管理系统,其数据库的部分关系模式如下: 用户:US
I/O设备管理软件一般分为4个层次,如下图所示。图中①②③分别对应( )。
部门、员工和项目的关系模式及它们之间的E-R图如下所示,其中,关系模式中带实下划
关系R.S如下表所示,元组演算表达式T={t|R(t)^?u(S(u)→t[3]
进程P1、P2、P3、P4和P5的前趋图如下图所示: 若用PV操作控制进程
聚类的典型应用不包括( ),( )是一个典型的聚类算法。 问题1选项 A
某PC的Inrernet协议属性参数如下图所示,默认网关的IP地址是( )。
某计算机系统页面大小为4K,进程的页面变换表如下所示。若进程的逻辑地址为2D16
随机试题
It’sbeen30yearssinceCongressrevisedUSpatentlawstoencourageuniver
Marydoesn’tseemtofavourtheideaofanewairportbecause______.[br][ori
[originaltext]Couldyouhelpmewiththeluggage,please?[/originaltext]A、Nopr
列宁关于“人的意识不仅反映客观世界,而且创造客观世界”的说法()A.夸大了意识
等截面连续梁构造简单,用于中小跨径时,梁高为()。A.(1/15~1/25)L
关于原地基处理要求正确的有()。A.原地面为坑,洞,穴等,应在清除沉积物后,用
导坑法中采用先拱后墙法的最大优点是()。A、施工快捷 B、施工安全 C、
共用题干 某开发公司获得一块30k㎡的土地用于经济适用房的建设,土地费用为10
如图由大体积水箱供水,且水位恒定,水箱顶部压力表读数19600Pa,水深H=2m
设f(x)是周期为2π的周期函数,它在[-π,π]上的表达式为:
最新回复
(
0
)