首页 > 试题广场 >

下列程序段的时间复杂度是for(int k =&nbs...

[单选题]
下列程序段的时间复杂度是
for(int k = 1; k <= n; k *= 2)
for(int j = k; j <= n; j++)
count++;
  • O(log2n)
  • O(n)
  • O(nlog2n)
  • O(n2)
for(int k=1; k<=n; k*=2) 这个循环最终执行的次数假设为x,则x次的时候k=2^x 。 当k>n时停止执行,于是2^x>n ,则可以认为该循环一共执行了log2n次。 加上内循环时间复杂度是nlog2n
发表于 2019-06-13 17:28:06 回复(0)