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

admin2019-12-10 34

问题设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://kaotiyun.com/show/ys3i777K

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

计算机408

学硕统考专业

相关试题推荐

“两个凡是”
一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。
对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接通过道路即可)，并要求增设的道路条数为最少，要解决这个问题，问：(1)
下列几种排序方法中，要求内存量最大的是()。
下图所示为双总线结构机器的数据通路，IR为指令寄存器，PC为程序计数器(具有自增功能)，M为主存(受R／W信号控制)，AR为地址寄存器，DR为数据缓冲寄存器，ALU由加、减控制信号决定完成何种操作，控制信号G控制的是一个门电路。另外，线上标注有小圈表示有控
某模型机的通路结构如下图所示，用寄存器传送语句(如PC→MAR)，拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0)，Y(R1)，源和目的操作数地址均采用变址寻址，第1个参数X为源操作数的形式地址，第2个参数为目的操作数的形
假设计算机系统采用CSCAN(循环扫描)磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。如果将磁盘替换为随机访问的Flash半导体存储器(如u盘、SSD等)，是否有比CSCAN更高效的磁盘调度策略?若有，给出磁盘调度策略的名称并说明
某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓存时间)分别为90ns、80ns、70ns、和60ns，则该计算机的CPU时钟周期至少是____。
设数据码字为10010011，采用汉明码进行校验，若仅考虑纠正一位错，则必须加入的(冗余)位数是()。

随机试题

备用离心泵，要求每天盘泵，机泵盘车的要求是()。
确定患者重型颅脑损伤深昏迷最有价值的体征是
乳痈患者，女性，28岁，乳房肿痛，壮热，皮肤掀红燥热，肿块软有应指感，舌红苔黄腻，脉洪数，应选用何方治疗
下列关于各国基金国际化的概况，说法正确的是()。Ⅰ．英国基金经常通过与东道国国内基金进行合作来进行国际化发售，以降低募集成本Ⅱ．卢森堡是欧洲第一个推行UCITS指令的国家，是目前全球最大的UCITS基金注册地Ⅲ．爱尔兰之所以成为广
制造企业的生产目的是为了将生产出来的物品通过销售环节转换成货币，为了销售生产经营的需要，制造企业所组织的物品实体应包括产成品、半成品、原材料和零配件等。()
2011年1—10月份，全国规模以上工业企业实现利润41217亿元，同比增长25．3％。10月当月实现利润4383亿元，同比增长12．5％。　　在规模以上工业企业中，国有及国有控股企业实现利润12519亿元，同比增长16．6％；集体企业实现利润676亿元
下列哪类人群正处在“延缓偿付期”?()
人生观是人们在实践中活动中所形成的关于人生目的和人生意义的根本看法，由三个部分组成。其中，回答人为什么活着属于
物理学家把由反粒子组成的物质称作反物质。1928年英国物理学家狄拉克预言反物质的存在。1997年美国科学家发现在银河系上方约3500光年处有一个不断喷射反物质的反物质源。2002年欧洲核子研究中心首次成功地对反物质原子的内部结构和物理特性进行了研究。从哲学
Theex-presidenthadbeen______inthecountrytorefreshhismindbeforehepassedaway.

最新回复(0)

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

计算机408

学硕统考专业

“两个凡是”

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。

下列几种排序方法中，要求内存量最大的是()。

某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓存时间)分别为90ns、80ns、70ns、和60ns，则该计算机的CPU时钟周期至少是____。

设数据码字为10010011，采用汉明码进行校验，若仅考虑纠正一位错，则必须加入的(冗余)位数是()。

备用离心泵，要求每天盘泵，机泵盘车的要求是()。

确定患者重型颅脑损伤深昏迷最有价值的体征是

乳痈患者，女性，28岁，乳房肿痛，壮热，皮肤掀红燥热，肿块软有应指感，舌红苔黄腻，脉洪数，应选用何方治疗

制造企业的生产目的是为了将生产出来的物品通过销售环节转换成货币，为了销售生产经营的需要，制造企业所组织的物品实体应包括产成品、半成品、原材料和零配件等。()

下列哪类人群正处在“延缓偿付期”?()

人生观是人们在实践中活动中所形成的关于人生目的和人生意义的根本看法，由三个部分组成。其中，回答人为什么活着属于

Theex-presidenthadbeen______inthecountrytorefreshhismindbeforehepassedaway.