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

admin2022-06-07 87

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

选项 A、O(n²109₂n)
B、O(nlo9₅n)
C、O(n²109₅n)
D、O(n³)

答案C

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

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

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

计算机408

学硕统考专业

相关试题推荐

Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是：仅当需要访问某页面时，如果它不在内存，把它调入内存。按照这个思路，将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理，也可以产生类似的算法，不妨称
某计算机存储器按字节编址，虚拟(逻辑)地址空间大小为16MB，主存(物理)地址空间大小为1MB，页面大小为4KB；Cache采用直接映射方式，共8行；主存与Cache之间交换的块大小为32B。系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如
循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是_______。
下列选项中，不可能是快速排序第2趟排序结果的是()。
设排序二叉树中结点的结构由三个域构成：数据域data，指向左儿子结点的指针域left，指向右儿子结点的指针域right。设data域为正整数，该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除。
标准的URI由3部分组成：服务器类型、主机名和路径及()。
E-mail中的存取协议IMAP与POP3协议的差别包括()。
流水CPU是由一系列叫做“段”的处理部件组成的。当流水稳定后的，和具备m个并行部件的CPU相比，一个m段流水CPU()。
在计算机的不同发展阶段，操作系统最先出现在()。
某指令流水线分为五级，分别完成取址(IF)、译码并取数(ID)、执行(EX)、访存(MEM)、写结果(WR)。设完成各阶段操作的时间依次为：90ns，60ns，70ns，100ns，50ns。试问：流水线的时钟周期应取何值?若第一条和第二条指令发

随机试题

DNA复制时，以序列5ˊCAGT-3ˊ为模板合成的互补结构是
患者步行300米即发生气喘，根据6分钟步行试验患者心功能严重程度为
祖冲之的代表作是()。
LucyandLilyaretwo______.Theyspeak______.
从儿童发展的立场来看，“兴趣”是儿童生命成长过程中对外界事物的一种内在冲动，是儿童内在生命力的一种表现形式，它并不是培养的结果。因此，从这个意义上来看，一些家长强迫孩子参加园外的很多兴趣班，结果往往事与愿违，影响了儿童的自然成长。这段话主要表达的观点是(
震慑的本意是震撼与威慑，其核心是不战而胜，起源于不战而屈人之兵的威慑理论。威慑的基础是实力，只有通过强大的实力和实战震慑，才能迫使对方不战而降。震慑依赖于瘫痪，瘫痪源于信息战装备和精确制导武器的合理使用。震慑理论首次运用于科索沃战争，继而在伊拉克战争中进行
设α，β，γ1，γ2，γ3都是4维列向量，且｜A｜=｜α，γ1，γ2，γ3｜=4，｜B｜=｜β，γ1，γ2，γ3｜=21，则｜A+B｜=________．
设总体X的概率分布为其中θ(0＜θ＜)是未知参数，利用总体X的如下样本值3，1，3，0，3，1，2，3，求θ的矩阵估计值和最大似然函数估计值。
Itwasabout600years______thatthefirstclockwasmade.
Whyisthecallbeingmade?

最新回复(0)

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

计算机408

学硕统考专业

循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是_______。

下列选项中，不可能是快速排序第2趟排序结果的是()。

标准的URI由3部分组成：服务器类型、主机名和路径及()。

E-mail中的存取协议IMAP与POP3协议的差别包括()。

流水CPU是由一系列叫做“段”的处理部件组成的。当流水稳定后的，和具备m个并行部件的CPU相比，一个m段流水CPU()。

在计算机的不同发展阶段，操作系统最先出现在()。

某指令流水线分为五级，分别完成取址(IF)、译码并取数(ID)、执行(EX)、访存(MEM)、写结果(WR)。设完成各阶段操作的时间依次为：90ns，60ns，70ns，100ns，50ns。试问：流水线的时钟周期应取何值?若第一条和第二条指令发

DNA复制时，以序列5ˊCAGT-3ˊ为模板合成的互补结构是

患者步行300米即发生气喘，根据6分钟步行试验患者心功能严重程度为

祖冲之的代表作是()。

LucyandLilyaretwo______.Theyspeak______.

设α，β，γ1，γ2，γ3都是4维列向量，且｜A｜=｜α，γ1，γ2，γ3｜=4，｜B｜=｜β，γ1，γ2，γ3｜=21，则｜A+B｜=________．

设总体X的概率分布为其中θ(0＜θ＜)是未知参数，利用总体X的如下样本值3，1，3，0，3，1，2，3，求θ的矩阵估计值和最大似然函数估计值。

Itwasabout600years______thatthefirstclockwasmade.

Whyisthecallbeingmade?

LucyandLilyaretwo.Theyspeak.