(单选题)
下列程序段的时间复杂度是( )。
count=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j++)
count++;
A.O(n)
B.O(nlog2n)
C.O(log2n)
D.O(n2)
参考答案:B
参考解析:
题目中给出了一个2层的嵌套循环,循环“for(j=1;j<=n;j++)”的时间复杂度是O(n),循环“for(k=1;k<=n;k*=2)”:k从1开始,每次增加一倍,也就是以2t的速度增长,当k达到n时t=log2n,因此这一循环的时间复杂度是O(log2n),对于嵌套循环的整体复杂度是两层循环的复杂度的乘积,因此总体的时间复杂度是O(nlog2n)。故本题正确答案选B。
知识点:计算机系统概述 计算机 计算机基本知识 通用 公基
