设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 int i=1： while(i

admin2019-07-18 78

问题设n是描述问题规模的非负整数，下面程序片段的时间复杂度是(       )。
  int i=1：
  while(i<=n)
i=i*2：

选项 A、O(log₂n)
B、O(n)
C、O(nlog₂n)
D、O(n²)

答案A

解析这是一个比较有趣的问题。如果不仔细分析的话，可能会得到O(n)的结果。
关键在于分析出while语句执行的次数。由于循环体中，i=i*2，所以循环执行的次数是log₂n，由此可见，算法的时间复杂度不是由问题规模n直接决定，而是log₂n。

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

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

计算机408

学硕统考专业

相关试题推荐

试评述明末清初三大思想家顾炎武、黄宗羲、王夫之。
20世纪50年代到70年代初，西欧国家通过有效的社会经济政策，维持了经济相对稳定和持续发展。这些政策主要包括()①加强对经济的宏观管理②废除生产关系中封建落后因素③发展高科技和新兴产业④进行社会改革，稳定社会
晋察冀抗日根据地
一个TCP连接总是以1KB的最大段发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是
试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。
举例说明P、V操作为什么要求设计成原语(即对同一信号量上的操作必须互斥)。P(S)操作：S．value--；If(S．value＜0){AddthisprocesstoS．L；Block()；
假定在一个处理机上执行的操作如下：作业估计服务时间片优先数A103B11C23D14E52这些
下图所示为双总线结构机器的数据通路，IR为指令寄存器，PC为程序计数器(具有自增功能)，M为主存(受R／W信号控制)，AR为地址寄存器，DR为数据缓冲寄存器，ALU由加、减控制信号决定完成何种操作，控制信号G控制的是一个门电路。另外，线上标注有小圈表示有控
设计一个判别表达式中左右括号是否配对出现的算法，采用()数据结构最佳。
某16位计算机中，带符号整数用补码表示，数据Cache和指令cache分离。题44表给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，mem表示存储单元地址，(x)表示寄存器x或存储单元x的内容。该计算机采用5段流水方式执行指令，各流水段分别是取指(

随机试题

多股钢丝绳的股丝越多，股内钢丝越细越多，钢丝绳的刚度也越好。
在工艺管道及仪表流程图中，管道上的阀门是用粗实线按标准规定的图形符号在相应处画出。
小林的亲属是精神分裂症患者目前在社区康复，其希望了解根据《重性精神疾病管理治疗工作规范》规定社区精神病患每年应至少进行1次健康检查，检查项目有哪几类()
小便灼热刺痛者为尿血而痛者为
A．尿频尿急，尿道灼痛，尿黄短少B．头痛目赤，急躁易怒，胁痛便秘C．腹部痞闷，纳呆便溏，面目发黄D．腹痛下痢，赤白粘冻，里急后重E．阴囊湿疹，瘙痒难忍，小便短赤肝胆湿热可见()
A．酸枣仁汤B．归脾汤C．五仁丸D．三仁汤E．天王补心丹方中同用酸枣仁、柏子仁，五味子的方剂是
患者，女。心脏联合瓣膜病10年，发热1月，体温为37．2～37．6℃，厌食，消瘦，贫血貌。确诊手段首选
在建设工程目标控制措施中，(　　)是其他措施的前提和保障。
活动表现评价是一种值得倡导的评价方式。活动表现评价应体现()。①独立性②综合性③实践性④理论性⑤开放性
A、Sheistryingtopersuadethemantoattendtherock-climbingclass.B、Sheistryingtotellthemanmanystudentsareinteres

最新回复(0)

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 int i=1： while(i

计算机408

学硕统考专业

试评述明末清初三大思想家顾炎武、黄宗羲、王夫之。

20世纪50年代到70年代初，西欧国家通过有效的社会经济政策，维持了经济相对稳定和持续发展。这些政策主要包括()①加强对经济的宏观管理②废除生产关系中封建落后因素③发展高科技和新兴产业④进行社会改革，稳定社会

晋察冀抗日根据地

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

举例说明P、V操作为什么要求设计成原语(即对同一信号量上的操作必须互斥)。P(S)操作：S．value--；If(S．value＜0){AddthisprocesstoS．L；Block()；

假定在一个处理机上执行的操作如下：作业估计服务时间片优先数A103B11C23D14E52这些

设计一个判别表达式中左右括号是否配对出现的算法，采用()数据结构最佳。

多股钢丝绳的股丝越多，股内钢丝越细越多，钢丝绳的刚度也越好。

在工艺管道及仪表流程图中，管道上的阀门是用粗实线按标准规定的图形符号在相应处画出。

小林的亲属是精神分裂症患者目前在社区康复，其希望了解根据《重性精神疾病管理治疗工作规范》规定社区精神病患每年应至少进行1次健康检查，检查项目有哪几类()

小便灼热刺痛者为尿血而痛者为

A．尿频尿急，尿道灼痛，尿黄短少B．头痛目赤，急躁易怒，胁痛便秘C．腹部痞闷，纳呆便溏，面目发黄D．腹痛下痢，赤白粘冻，里急后重E．阴囊湿疹，瘙痒难忍，小便短赤肝胆湿热可见()

A．酸枣仁汤B．归脾汤C．五仁丸D．三仁汤E．天王补心丹方中同用酸枣仁、柏子仁，五味子的方剂是

患者，女。心脏联合瓣膜病10年，发热1月，体温为37．2～37．6℃，厌食，消瘦，贫血貌。确诊手段首选

在建设工程目标控制措施中，( )是其他措施的前提和保障。

活动表现评价是一种值得倡导的评价方式。活动表现评价应体现()。①独立性②综合性③实践性④理论性⑤开放性

A、Sheistryingtopersuadethemantoattendtherock-climbingclass.B、Sheistryingtotellthemanmanystudentsareinteres

在建设工程目标控制措施中，(　　)是其他措施的前提和保障。