首页 > 试题广场 >

下列程序段的时间复杂度是（ ...

[单选题]

下列程序段的时间复杂度是（）

count = 1；
for(k=1;k<2n;k*=2)
for(i=1;i<4n;i+=2)
count++;

查看正确选项

不上岸就不改名

我怀疑题目的代码有缩进错误，原来的代码应该是这样的：

count = 1；
for(k=1;k<2n;k*=2)
    for(i=1;i<4n;i+=2)
count++;

这样第一个循环的O(log2n)和第二个循环的O(n)的复杂度才是相乘的关系

发表于 2019-08-15 19:07:49 回复(0)

大铁牛仔裤

假设外层循环a次，内层循环b次，外层2的a次方＞＝2n解得a＞＝log2n+1所以外层是log2n 内层是1首项2公差的等差数列，b+（b-1）2＞＝4n解得b＞4/3n+2/3内层是n

编辑于 2020-11-27 21:13:02 回复(0)

提交观点

问题信息

算法工程师复杂度 2018 360集团

来自：360公司-2018春...

上传者：小小

难度：

2条回答 5收藏 2428浏览

扫一扫，把题目装进口袋