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

admin2020-06-17 23

问题设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://jikaoti.com/ti/uNDjFFFM

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

计算机408

学硕统考专业

相关试题推荐

设有一个双向链表h，每个结点中除有prior，data和next三个域外，还有一个访问频度域freq，在链表被起用之前，每个结点中的freq域都被初始化为零。每当进行LocateNode(h，x)运算时，令元素值为x的结点中freq域中的值加一，并调整表中
每棵树都能唯一地转换成相对应的二叉树，由树转换成的二叉树中，一个结点N的左孩子是它在原树对应结点的()。
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令，平均每条指令需要5个机器周期，其中3个周期必须访问内存，内存读写需一个机器周期，假定CPU在95％的时间内持续执行“背景程序”，且这段时间内不执行I／O指令。现
如下图所示为一个TCP主机中的拥塞窗口的变化过程，这里最大数据段长度为1024字节，请回答如下问题：本次传输是否有发生超时?如果有是在哪一次传输超时?
荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。
设一段正文由字符集{A，B,C，D，E，F}中的字母组成，这6个字母在正文中出现的次数分别为{12，18，26，6，4，34}。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成，试计算按哈夫曼编码压缩存储这段正文共需多少个字节。(3)若
给定序列{3，5，7，9，11，13，15，17}，按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均查找长度。
已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(keyl
栈S最多只能容纳4个元素，现在6个元素按A，B，C，D，E，F的顺序进栈，下列哪一个序列是可能的出栈序列()?

随机试题

A、Hehadanaccident.B、Heoverslept.C、Hegotstuckinatrafficjam.D、Heforgotthetime.C女士询问男士为什么那么晚，火车四十分钟前就离开了；男士表示抱歉并解释
五四运动的直接导火线是()
阅读《说笑》的第四段：所以，幽默至多是一种脾气，决不能标为主张，更不能当作职业。我们不要忘掉幽默(humour)的拉丁文原意是液体；换句话说，好象贾宝玉心目中的女性，幽默是水做的。把幽默当为一惯的主义或一生的衣食饭碗，那便是液体凝为固体，生物制成
肝的上界在右锁骨中线相交于【】
产褥中暑的临床表现有哪些?
下列选项中由卫生部制定的是()
小张出差回来报销旅费2700元，原借3000元，交回多余现金300元。则报销时的会计分录为()。
WilliamWordsworthisanEnglish______.
试论犯罪的基本特征。(2018年一法专一第35题)
设随机变量X服从参数为λ的泊松分布，且P(X=0)=P(X=1)，则P(X≥1)=________．

最新回复(0)

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

计算机408

学硕统考专业

每棵树都能唯一地转换成相对应的二叉树，由树转换成的二叉树中，一个结点N的左孩子是它在原树对应结点的()。

如下图所示为一个TCP主机中的拥塞窗口的变化过程，这里最大数据段长度为1024字节，请回答如下问题：本次传输是否有发生超时?如果有是在哪一次传输超时?

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

给定序列{3，5，7，9，11，13，15，17}，按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均查找长度。

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

栈S最多只能容纳4个元素，现在6个元素按A，B，C，D，E，F的顺序进栈，下列哪一个序列是可能的出栈序列()?

A、Hehadanaccident.B、Heoverslept.C、Hegotstuckinatrafficjam.D、Heforgotthetime.C女士询问男士为什么那么晚，火车四十分钟前就离开了；男士表示抱歉并解释

五四运动的直接导火线是()

肝的上界在右锁骨中线相交于【】

产褥中暑的临床表现有哪些?

下列选项中由卫生部制定的是()

小张出差回来报销旅费2700元，原借3000元，交回多余现金300元。则报销时的会计分录为()。

WilliamWordsworthisanEnglish______.

试论犯罪的基本特征。(2018年一法专一第35题)

设随机变量X服从参数为λ的泊松分布，且P(X=0)=P(X=1)，则P(X≥1)=________．