下列程序段的时间复杂度是 count=0： for(k=1；k

admin2022-06-07 9

问题下列程序段的时间复杂度是
  count=0：
  for(k=1；k<=n；k*=2)
  for(j=1；j<=n；j++)
         count++：

选项 A、O(log2n)
B、O(n)
C、O(nlog₂n)
D、O(n²)

答案C

解析题目中给出了一个2层的嵌套循环，循环“for(j=1；j<=n；j++)”的时间复杂度是O(n)，循环“for(k=1；k<=n；k*=2)”：k从1开始，每次增加一倍，也就是以2^t的速度增长，当k达到n时t=log₂n，因此这一循环的时间复杂度是D(log₂n)，对于嵌套循环的整体复杂度是两层循环的复杂度的乘积，因此总体的时间复杂度是O(nlog₂n)。

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

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