假设n是描述问题规模的非负整数，下面程序片段的时间复杂度为( )。 void fun(int n){ int i，j，k； for(i=1;i＜=n;i++) for(j=1;j＜=n;j++){ k=1； while(k＜=n k=5*k;

admin2019-12-10 38

问题假设n是描述问题规模的非负整数，下面程序片段的时间复杂度为( )。
void fun(int n){
int i，j，k；
for(i=1;i＜=n;i++)
for(j=1;j＜=n;j++){
k=1；
while(k＜=n
k=5*k;
}
}

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

答案C

解析首先抓基本运算语句，即k=5*k；设其执行时间为T(n)。对于j每循环一次，该语句的执行次数为m，有5^m≤n，即m≤log₅n。所以，
T(n)=∑ⁿ_i=1∑ⁿ_j=1m=m∑ⁿ_i=1∑ⁿ_j=1=mn²=n²log₅n=O(n²log₅n)

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

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

计算机408

学硕统考专业

相关试题推荐

任意给定1，2……．，n指定为一棵树的先根遍历序列；同时任意给定这n个数值(1，2……．，n)的一个排列p1，p2……．pn为这棵树的后根遍历序列。(1)根据这样的先根遍历序列和后根遍历序列，是否都可以得到一棵树?如果能够，请简述理由(不要求形式化证明)
将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较次数是()。
某图形显示器的分辨率为640×480，刷新频率为50Hz，且假定水平回扫期和垂直回扫期各占水平扫描周期和垂直扫描周期的20％，试计算图形显示器的行频、水平扫描周期、每个像素的读出时间和视频带宽。若分辨率提高到1024×768，刷新频率提高到60Hz，再次计
有关虚拟设备的论述中，正确的是()。
若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是()。
在某计算机中采用了多级存储体系，设计有cache，主存和磁盘，假设访问cache一个字需要花费10ns，若该字不在cache中但是存在在主存中，那么需要100ns载入cache，然后重新开始定位。若该字既不在cache中，也不在主存中，那么需要10ms的时
图的D搜索类似于BFS。不同之处在于使用栈代替BFS中的队列，入／出队列的操作作为入／出栈的操作，即当一个顶点的所有邻接结点被搜索后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。用邻接表作为存储结构，写一个D搜索算法；
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令，平均每条指令需要5个机器周期，其中3个周期必须访问内存，内存读写需一个机器周期，假定CPU在95％的时间内持续执行“背景程序”，且这段时间内不执行I／O指令。现
某阅览室晚间开放，第一个进入的读者开灯，最后一个离开的读者关灯。利用P、V原语操作实现读者进程。

随机试题

在《季氏将伐颛臾》一文所运用的论据中，下列属于理论论据的是()
招标人与投标人之间的博弈，在采购合同签订后，两者之间的招标与投标关系转化为买卖关系，博弈的类型也相应地发生变化，买卖双方形成一种合作博弈的关系，原因在于双方对于合同()等方面目标的一致性要多于分歧。
通电检验的逐级顺序原则是()。
措施项目费的计算，下列说法正确的有()。
下列论述不正确的是()
长城公司为上市公司(以下简称长城公司)，为增值税一般纳税人，适用的增值税税率为17％。原材料按计划成本进行日常核算。期末原材料按成本与可变现净值孰低法计量，每月月末原材料按品种计提存货跌价准备。2011年12月31日，长城公司部分原材料情况如下表：
甲股份有限公司(本题下称甲公司)为增值税—般纳税人，适用的增值税税率为17％。甲公司适用的所得税税率为25％。所得税采用资产负债表债务法核算。甲公司2011年度所得税汇算清缴于2012年4月30日完成，在此之前发生的2011年度纳税调整事项，均可进行纳税
关于古琴，下列说法不正确的是：
民族精神集中体现了一个民族在一定自然环境和社会历史条件下生存与发展的独特方式，反映了一个民族的心理特征、文化传统和精神风貌．是一个民族赖以生存和发展的精神支柱。中华民族精神的内涵十分丰富，爱国主义是其核心，同时包括了团结统一、爱好和平、勤劳勇敢、自强不息在
Thisseminarwillgiveparticipantstipsonhowto______alargeteamofstaffmembers.

最新回复(0)

假设n是描述问题规模的非负整数，下面程序片段的时间复杂度为( )。 void fun(int n){ int i，j，k； for(i=1;i＜=n;i++) for(j=1;j＜=n;j++){ k=1； while(k＜=n k=5*k;

计算机408

学硕统考专业

将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较次数是()。

有关虚拟设备的论述中，正确的是()。

若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是()。

某阅览室晚间开放，第一个进入的读者开灯，最后一个离开的读者关灯。利用P、V原语操作实现读者进程。

在《季氏将伐颛臾》一文所运用的论据中，下列属于理论论据的是()

招标人与投标人之间的博弈，在采购合同签订后，两者之间的招标与投标关系转化为买卖关系，博弈的类型也相应地发生变化，买卖双方形成一种合作博弈的关系，原因在于双方对于合同()等方面目标的一致性要多于分歧。

通电检验的逐级顺序原则是()。

措施项目费的计算，下列说法正确的有()。

下列论述不正确的是()

关于古琴，下列说法不正确的是：

Thisseminarwillgiveparticipantstipsonhowto______alargeteamofstaffmembers.