首页 > 试题广场 >

题目来源于王道论坛 下列程序段的时间复杂度是

[单选题]
下列程序段的时间复杂度是  
count = 0;
for (int k = 1; k <= n; k *= 2)
    for (int j = 1; j <= n; j++)
        count++;
  • O(log(n))
  • O(n)
  • O(nlog(n))
  • O(n^2)
添加回答
推荐
zsw3头像 zsw3

解析：

内层循环条件j<=n与外层循环的变量无关，每次循环j自增1，每次内层循环都执行n次。外层循环条件为k<=n，增量定义为k*=2，可知循环次数为2k<=n，即k<=log2n。所以内层循环的时间复杂度是O(n)，外层循环的时间复杂度是O(log2n)。对于嵌套循环，根据乘法规则可知，该段程序的时间复杂度T(n)=T1(n)*T2(n)=O(n)*O(log2n)=O(nlog2n)，选C。

发表于 2018-06-16 11:37:18 回复(0)
JG专用头像 JG专用

外层循环次数: 1 2 3 4 5 ...

循环末尾k值: 2 4 8 16 32...

所以2^k=n,即外层循环logn次

内层循环n次

乘法法则得O(nlogn)

发表于 2020-03-01 16:24:28 回复(0)
有一套的小飞象想当offer收割机头像 有一套的小飞象想当offer收割机
第一个for循环里最后是k*2，所以时间复杂度为O（logn）要仔细看看，然后二层for循环是O（n）,最后一乘为 O（nlogn）
发表于 2022-11-07 08:33:25 回复(0)
纠结的哈士奇在笔试头像 纠结的哈士奇在笔试
外loop：O（logn）；内loop：O（n）；总时间复杂度：O（n·logn）
发表于 2023-06-26 12:08:12 回复(0)
牛客73365540号头像 牛客73365540号
对于嵌套循环，程序时间复杂度相乘。
发表于 2023-06-14 16:08:27 回复(0)
提交观点

问题信息

复杂度
上传者：zsw3
难度：
5条回答 2939浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号