设n是描述问题规模的非负整数，下列程序段的时间复杂度是( )。

admin2020-06-17 24

问题设n是描述问题规模的非负整数，下列程序段的时间复杂度是( )。

选项 A、O(logn)
B、O(n^1/2)
C、O(n)
D、O(n²)

答案B

解析假设第k次循环终止，则第k次执行时，(x+1)²＞n，x的初始值为0，第k次判断时，x=k-1，即k²＞n，k＞n^1/2,，因此该程序段的时间复杂度为O(n^1/2)。选B。

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

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

计算机408

学硕统考专业

相关试题推荐

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。
设有一缓冲池P，P中含有10个可用缓冲区，一个输入进程将外部数据读入P，另有一个输出进程将P中数据取出并输出(如下图所示)。若进程每次操作均以一个缓冲区为单位，试用记录型信号量写出两个进程的同步算法，要求写出信号量的设置。输入进程输出进程L：读入数据L1;
在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(10gn)的算法，确定树中第k个结点的位置。
序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。
假定在一个处理机上执行的操作如下：这些作业假定按A、B、C、D、E次序先后几乎同时(时间差相对时间片大小忽略不计)到达。(1)给定相应的图示来说明分别用FcFS、RR(时间片=1)、SJF和非抢占优先调度算法(最小优先数有最高优先权)调度这些作业的情
荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。
某机字长32位，采用定长操作码，单字长指令，共有机器指令100条，CPU内部有通用寄存器32个，可作变址寄存器用，存储器按字节编址，指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。写出4种寻址方式下，有效地址EA的表达式。
设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离1w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。

随机试题

第一届中国人民政治协商会议召开于()
护理的对象是
国际标准化组织(ISO)和国际咨询工程师联合会(FIDIC)推荐采用国际通用的()循环方法进行过程控制。
无代价抵偿货物是指进出口货物在海关放行前，因残损、短少、品质不良或者规格不符等原因，由进出口货物的发货人、承运人或保险公司免费补偿或者更换的，与原货物相同或与合同规定相符的货物。()
旅行社招揽、接待旅游者，应当制作和保存完整的业务档案，保存期最低为()年。
根据记忆内容的性质可以将记忆分为陈述性记忆和()。
列举中国近代史五种史料，并简评之。(南京大学2008年中国近现代史复试真题)
Aslongaspeoplehavelookedupatthenightsky,theyhavewonderedwhetherhumanityisaloneintheuniverse.Ofplacesclose
在外部设备中，扫描仪属于
TheUnitedStatesiswell-knownforits【C1】______ofmajorhigherhighwaysdesignedtohelpa【C2】______getfromoneplacetoan

最新回复(0)

设n是描述问题规模的非负整数，下列程序段的时间复杂度是( )。

计算机408

学硕统考专业

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(10gn)的算法，确定树中第k个结点的位置。

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离1w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。

第一届中国人民政治协商会议召开于()

护理的对象是

国际标准化组织(ISO)和国际咨询工程师联合会(FIDIC)推荐采用国际通用的()循环方法进行过程控制。

无代价抵偿货物是指进出口货物在海关放行前，因残损、短少、品质不良或者规格不符等原因，由进出口货物的发货人、承运人或保险公司免费补偿或者更换的，与原货物相同或与合同规定相符的货物。()

旅行社招揽、接待旅游者，应当制作和保存完整的业务档案，保存期最低为()年。

根据记忆内容的性质可以将记忆分为陈述性记忆和()。

列举中国近代史五种史料，并简评之。(南京大学2008年中国近现代史复试真题)

Aslongaspeoplehavelookedupatthenightsky,theyhavewonderedwhetherhumanityisaloneintheuniverse.Ofplacesclose

在外部设备中，扫描仪属于

TheUnitedStatesiswell-knownforits【C1】______ofmajorhigherhighwaysdesignedtohelpa【C2】______getfromoneplacetoan

TheUnitedStatesiswell-knownforits【C1】ofmajorhigherhighwaysdesignedtohelpa【C2】getfromoneplacetoan