首页 > 试题广场 >

下列算法段中，时间复杂度为（）

[单选题]

下列算法段中，时间复杂度为（） 

for(i=1;i<=n;i++)
{
    for(j=1;j<=i;j++)
    {
        x=0;
        for(k=1;k<=n;k++)
            x+=a*b;
    }
}
  • O(n^2)
  • O(n^2*(n+1))
  • O(n*(n+1))
  • O(n^3)
添加回答
推荐
何博明头像 何博明
三重循环，实际循环次数为（1+2+3+...+n）*n，O计算时间复杂度忽略常数系数，且只保留最高项.。综上，选D
编辑于 2017-03-18 09:05:34 回复(1)
##头像 ##
三层循环，每层最多都是n，所以一共的时间复杂度为n^3，选D
发表于 2017-01-13 10:11:13 回复(3)
Two Cold头像 Two Cold
列个方程算一算就好，可以把第三个for提出来，因为和其它的都没什么关联，然后第一个和第二个for是1+2+。。。的和，这个是n^2数量级的，最后总的是n^3数量级的，因此是D
发表于 2017-01-13 18:19:24 回复(0)
哎呦呦呦呦丁头像 哎呦呦呦呦丁
n(n+1)/2*n~o(n^3)
发表于 2017-01-13 17:28:30 回复(0)
改个名字哈头像 改个名字哈
最内层x+=a*b为基本语句 当I=A,j=B时，最内层循环循环了(1+2+3+...+B)*n次。 那么I=n,j=n时，最内层循环循环了(1+2+3+...+n)*n次。 最高次幂为n^3 可知时间复杂度为o(n^3)
发表于 2017-09-05 21:51:13 回复(0)
际头像 际 
表示上两层循环i和j，k循环次数是n，所以一共循环(1+n)*(n^2)/2次，时间复杂度为O(n^3),选D

发表于 2017-01-13 13:13:35 回复(0)
非常凡想头像 非常凡想
时间复杂度省略常数，低阶
发表于 2020-01-10 13:44:22 回复(0)
混吃等死的咸鱼本鱼头像 混吃等死的咸鱼本鱼
看错了。。看成两层循环了
发表于 2019-04-10 17:41:42 回复(0)
做个程序员头像 做个程序员
i层是n，j层是（1+n）*n/2也就是n^2，k层实际上是求的a*b*n，没有循环，因此n^3
发表于 2017-08-16 22:50:47 回复(1)
zaynmalik头像 zaynmalik
选D，三层循环，每一层都是n ,n*n*n
发表于 2017-01-13 19:44:44 回复(0)
blythe头像 blythe
最外层for循环复杂度为：
       o(n)
第二层和第三层同样为：
o(n)

所以为D
发表于 2017-01-13 10:11:25 回复(0)
提交观点

问题信息

复杂度
来自：顺丰2017校招研发工...
上传者：牛100
难度：
11条回答 5873浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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