首页 > 试题广场 >

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

[单选题]

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

count=0;
for(k=1;k<=n;k*=2)
    for(j=1;j<=n;j++)
        count++;

查看正确选项

agjsytt

法则: 嵌套for循环的时间复杂度=最内层循环一条语句的总的运行时间*各层循环的大小(循环次数). 注:所有时间均为单位时间.

本题中.

最内层循环一条语句的总的运行时间:1;

内层循环大小(循环次数):n

外层循环大小(循环次数)：log(2)n. 因为设外层循环x次,则2^x=n,那么x=log(2)n.

合计:1*n*log(2)n

编辑于 2017-02-19 21:43:53 回复(2)

毛姝垚

发表于 2022-11-29 16:19:36 回复(0)

二咩

外层循环log2n次，内层每次都是循环n次，所以复杂度为o(nlog2n)

发表于 2016-12-01 12:39:59 回复(0)

提交观点

问题信息

复杂度

上传者：城市里的养猫者

难度：

3条回答 57收藏 6850浏览

扫一扫，把题目装进口袋