首页 > 试题广场 >

下列程序的时间复杂度是？

[单选题]
下列程序的时间复杂度是（）
for (int i = 1, s = 0; i <= n; ++i)
{
    int t = 1;
    for (int j = 1; j <= i; ++j)
        t = t * j;
    s = s + t;
}


  • O(n)
  • O(n*logn)
  • O(n^2)
  • O(n^3)
添加回答
推荐
牛客-007头像 牛客-007
答案：C
时间复杂度只跟循环有关，跟常数级操作无关。因为时间复杂度是取数量级的，而不是具体计算次数。所以这个程序的时间复杂度等价于：
for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= i; ++j)
这两层循环，外层执行n次，内存平均执行n/2次，时间复杂度为O(n^2)
编辑于 2015-01-28 17:56:16 回复(0)
Yano_nankai头像 Yano_nankai

执行次数分别为1 2 3 ... n

所以总的执行次数是1到n的和，为n*(1+n)/2，时间复杂度是O(n^2)

发表于 2015-08-06 16:50:54 回复(1)
牛客651205号头像 牛客651205号
当 i==n 的时候就是标准的O(N^2),所以按照对高次幂开说就是O(N^2)
发表于 2019-02-18 16:08:56 回复(0)
牛客872009786号头像 牛客872009786号
C,2层循环
发表于 2020-03-22 11:48:20 回复(0)
单程车票头像 单程车票
Ｃ
时间复杂度，２层for循环
发表于 2015-01-21 13:12:54 回复(0)
提交观点

问题信息

复杂度
来自：2015年度信息化技能...
上传者：小牧魔法袋
难度：
5条回答 13775浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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