首页 > 试题广场 >

程序段 for(i=n-l;il;i--) for(j

[单选题]

程序段如下所示，其中n为正整数，则最后一行的语句在最坏情况下的时间复杂度是（）

int tmp;
for (int i = n - 1; i > 1; i--) {
    for (int j = 1; j < i; j++) {
        if (A[j] > A[j + 1]) {
            tmp = A[j];
            A[j] = A[j + 1];
            A[j + 1] = tmp;
        }
    }
}

```
O(n)
```
```
O(n²)
```
```
O(n*log₂n)
```
```
不直接依赖于n
```

推荐

缓缓故人归

答案：B

解析：最坏的情况当然就是 A[j]>A[j+1] 一直满足而使得 A[j]与A[j+1] 的对换总是发生啦。所以问题归结为两个 for 的执行次数是多少。

外层 i 的执行范围是 l~n-l 共（n-2l）次，内层 j 的执行范围是 l~i 共（i-l）次。另外应该明白的是，内层 l~i 执行完整一遍的时候，外层 l~n-1 只执行其中一步。当 i==l+1，此时内层 l~i 执行次数最小是 1 次（l+1-l），这同时也是外层 for 的最后一次循环。当 i==n-l，此时内层 l~i 执行次数最大是 n-2l 次（n-l-l），这同时也是外层 for 的第一次循环。因此，这个等差数列的和就是 (1+n-2l)*(n-2l)/2，也就是 O(n2)。

编辑于 2019-12-27 14:15:49 回复(2)