假设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 24

问题假设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

学硕统考专业

相关试题推荐

假设在一台单处理机上执行如下表所示的进程，且假定这些进程在时刻0以1，2，3，4，5的顺序创建。时间单位为时间片，优先级以数值大者为优。(1)请说明分别使用FCFS、RR(时间片＝1)、SPF以及非抢夺式优先级调度算法时，这些进程的执行情况。(2)争
一台模型机共有7条指令，主频25MHz，各指令的使用频率与CPI如下表所示，该机有8位和16位两种指令字长，采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型，16位字长指令为寄存器一存储器(R—M)二地址变址类型(地址码范围在－128
计算机操作系统中，若WAIT、SIGNAL操作的信号量S初值为3，当前值为一2，则表示当前有()个等待信号量S的进程。
编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
不需要抢占的进程调度算法是()。
MS-DOS中的文件物理结构采用()。
主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的lP地址为211．68．71．80。H与S使用TCP通信时，在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。根据题47一a表中的IP分组，分析s已经
某16位计算机中，带符号整数用补码表示，数据Cache和指令cache分离。题44表给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，mem表示存储单元地址，(x)表示寄存器x或存储单元x的内容。该计算机采用5段流水方式执行指令，各流水段分别是取指(
主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的IP地址为211．68．71．80。H与S使用TCP通信时，在H上捕获的其中5个IP分组如表5-1所示。回答下列问题：表5-1中的IP分组中，哪几个是由H发送的?

随机试题

一定限度内动机强度和问题解决的效率成正比，()等强度的动机是问题解决的最佳水平。
房地产开发项目融资资金的来源渠道主要有自有资金、银行信贷、______和其他融资。
(2009年)下列波函数不合理的是()。
根据《建设工程质量管理条例》，关于建设工程最低保修期限的说法正确的有()。
对于局部应用系统的A类火灾场所，中倍数泡沫灭火系统的泡沫连续供给时间不应小于()min。
下列支出中，属于消费性支出的有()。
从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性：
下列测验能用于测量个人在音乐、美术、体育、机械、飞行等方面才能的是
1896年发表了标志着芝加哥机能心理学派的正式诞生的《心理学中的反射弧概念》的人物是()。
请看下图回答以下问题。[首都师范大学2016]简述这类实验的显著性检验方法。

最新回复(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

学硕统考专业

计算机操作系统中，若WAIT、SIGNAL操作的信号量S初值为3，当前值为一2，则表示当前有()个等待信号量S的进程。

编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。

不需要抢占的进程调度算法是()。

MS-DOS中的文件物理结构采用()。

主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的lP地址为211．68．71．80。H与S使用TCP通信时，在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。根据题47一a表中的IP分组，分析s已经

主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的IP地址为211．68．71．80。H与S使用TCP通信时，在H上捕获的其中5个IP分组如表5-1所示。回答下列问题：表5-1中的IP分组中，哪几个是由H发送的?

一定限度内动机强度和问题解决的效率成正比，()等强度的动机是问题解决的最佳水平。

房地产开发项目融资资金的来源渠道主要有自有资金、银行信贷、______和其他融资。

(2009年)下列波函数不合理的是()。

根据《建设工程质量管理条例》，关于建设工程最低保修期限的说法正确的有()。

对于局部应用系统的A类火灾场所，中倍数泡沫灭火系统的泡沫连续供给时间不应小于()min。

下列支出中，属于消费性支出的有()。

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性：

下列测验能用于测量个人在音乐、美术、体育、机械、飞行等方面才能的是

1896年发表了标志着芝加哥机能心理学派的正式诞生的《心理学中的反射弧概念》的人物是()。

请看下图回答以下问题。[首都师范大学2016]简述这类实验的显著性检验方法。