首页 > 试题广场 >

下面程序的时间复杂度为( ) for ( i=1 , s=0

[单选题]
下面程序的时间复杂度为(
for (int i = 1, s = 0; i <= n; i++) {
    int t = 1;
    for (int j = 1; j <= i; j++) t *= j;
    s += t;
}
  • O(n)
  • O(n^2)
  • O(n^3)
  • O(n^4)

第二层循环每次循环i次,而i是从1...n

所以循环要进行1+2+3+4+...+n次

即时间频率T(n)=n(n+1)/2=(n^2+n)/2

因为算法的时间复杂度一般只考虑n的最高次项

即O(n^2)


选B

发表于 2020-03-01 16:09:42 回复(0)
考虑最高阶,乘法耗时间久。t*=j。i是几,就累乘到几,执行1+2+3+4+...+n=n(n+1)/2所以就是O(n* n)
发表于 2022-10-11 07:40:20 回复(0)
B
发表于 2018-04-27 13:57:57 回复(1)