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

[单选题]

下列程序段的时间复杂度是（）
count = 1；
for(k=1;k<2n;k*=2)
for(i=1;i<4n;i+=2)
count++;

查看答案及解析

一起的远方

多层嵌套采用的是乘法原则，即嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。对于此题，O(n)=T1(n) * T2(n)，其中T2(n)即是第二层的时间的复杂度，对其单独分析的时间复杂度是 n；第一层我们重点分析一下：

将for(k=1; k<2n; k*=2) 转换为 while(k < 2n) k = k*2，这种形式应该见过吧，不就是等比数列嘛，通过对 2^x = n 求解可知 x = log2n，即是 T1(n) = log2n。

所以 O(n)=T1(n) * T2(n) = n * log2n。

发表于 2019-08-27 18:56:17 回复(0)

提交观点

问题信息

前端工程师复杂度 2018 360集团

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

上传者：小小

难度：

1条回答 11收藏 1635浏览

扫一扫，把题目装进口袋