问题
单项选择题
下列程序段的时间复杂度是
count=0;
for(k=1;k＜=n;k*=2)
for(j=1;j＜=n;j++)
count++;
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
答案
参考答案：C
解析： 题目中给出了一个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)。