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

admin2019-12-10 38

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

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

计算机408

学硕统考专业

相关试题推荐

某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns，命中率为p1；若Cache未命中，CPU需直接访问主存，访问时间为t2ns，主存命中率为p2；若所需数据字不在主存中，则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。
已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。
下图是三个计算机局域网A，B和C，分别包含10台，8台和5台计算机，通过路由器互联，并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61．60．21．80的互联网地址)。LANA和LANB公用一个C类IP地址
5位二进制定点小数，用补码表示时，最小负数是()。
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题足找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路
以下关于CPU的叙述中，错误的是()。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50ms，输
CRT显示器显示图形图像的原理是图形图像()。

随机试题

Wenowobtainmorethantwo-thirdsofourproteinfromanimalsources,whileourgrandparents______onlyone-halffromanimalso
以甘油一酯途径合成三酰甘油主要存在于
沙门菌食物中毒的食品主要为蛋类和家禽肉，是因为
药物相互作用对药动学的影响A．与多潘立酮配伍B．甲苯磺丁脲配伍氢氯噻嗪C．磺胺类药与青霉素配伍D．与大环内酯类抗生素配伍E．阿司匹林与磺酰脲类降糖药合用影响分布()。
下列对框架建筑优缺点的表述中，正确的有()。
“进行招标策划，确定投标报价及其策略并确定承包合同价”是()阶段的造价管理内容。
资产负债表的下列项目中，需要根据几个总账账户的期末余额进行汇总填列的是()。
角色中断是指在一个人前后相继所承担的两种角色之间发生了矛盾的现象。根据上述定义，下列属于角色中断的是()。
2015年上半年，A市新设内资企业20518，注册资本(金)1651．8亿元，同比分别增长39．7％和133％。其中私营企业20187户，注册资本(金)1258．76亿元，同比分别增长30．4％和224％。从设立总量来看，批发零售业、制造业、
ReadingforpleasureistheeasiestwaytobecomeabetterreaderinEnglish.Itisalsothemostimportantway.Somestuden

最新回复(0)

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

计算机408

学硕统考专业

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

已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。

5位二进制定点小数，用补码表示时，最小负数是()。

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

以下关于CPU的叙述中，错误的是()。

CRT显示器显示图形图像的原理是图形图像()。

Wenowobtainmorethantwo-thirdsofourproteinfromanimalsources,whileourgrandparents______onlyone-halffromanimalso

以甘油一酯途径合成三酰甘油主要存在于

沙门菌食物中毒的食品主要为蛋类和家禽肉，是因为

药物相互作用对药动学的影响A．与多潘立酮配伍B．甲苯磺丁脲配伍氢氯噻嗪C．磺胺类药与青霉素配伍D．与大环内酯类抗生素配伍E．阿司匹林与磺酰脲类降糖药合用影响分布()。

下列对框架建筑优缺点的表述中，正确的有()。

“进行招标策划，确定投标报价及其策略并确定承包合同价”是()阶段的造价管理内容。

资产负债表的下列项目中，需要根据几个总账账户的期末余额进行汇总填列的是()。

角色中断是指在一个人前后相继所承担的两种角色之间发生了矛盾的现象。根据上述定义，下列属于角色中断的是()。

2015年上半年，A市新设内资企业20518，注册资本(金)1651．8亿元，同比分别增长39．7％和133％。其中私营企业20187户，注册资本(金)1258．76亿元，同比分别增长30．4％和224％。从设立总量来看，批发零售业、制造业、

ReadingforpleasureistheeasiestwaytobecomeabetterreaderinEnglish.Itisalsothemostimportantway.Somestuden