首页 > 试题广场 >

下面算法的时间复杂度是（）

[单选题]

下面算法的时间复杂度是（）

for (int i = n; i > 1; i--) {
    for (int j = i - 1; j > 1; j--) {
        x++;
    }
}

```
O(n)
```
```
O(n^2)
```
```
O(n(n-1))
```
```
O(nlog(n))
```

查看正确选项

二咩

(n-2)+(n-3)+...+2+1=(n-1)*(n-2)/2,复杂度计算的是最高阶的规模,所以是o(n^2)

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

大星星和小猩猩

时间复杂度/空间复杂度都是只看最高阶。

发表于 2018-05-01 18:39:39 回复(0)

大胡子蒙蒙

这个算法的时间复杂度可以通过分析内层循环和外层循环的执行次数来确定。外层循环执行了 n - 1 次（因为 i 从 n 开始，递减到 2，共执行了 n - 1 次）。内层循环的执行次数取决于外层循环的当前值。当 i = n 时，内层循环执行了 n - 2 次；当 i = n - 1 时，内层循环执行了 n - 3 次；以此类推，当 i = 2 时，内层循环执行了 1 次。因此，内层循环的总执行次数可以表示为 (n-2) + (n-3) + ... + 1，这是一个等差数列，其和为 (n-1)(n-2)/2。因此，该算法的时间复杂度可以表示为 O(n^2)。

发表于 2023-11-15 03:33:41 回复(0)