CSP-S 2019 第一轮 第20题：（3分）若输入的a数组是一个严格单调递增的数列，此程序的时间复

题目

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

（3 分）若输入的 $a$ 数组是一个严格单调递增的数列, 此程序的时间复杂度（）

选项

• A. $O(\log n)$
• B. $O(n^2)$
• C. $O(n\log n)$
• D. $O(n)$

答案

D

题解

选 D．\(O(n)\)。

因为数组严格递增，所以 a[i] < a[i - 1] 永远不成立，ans 不会被重置。

观察 while：

• 当 i = 1 时，ans = 1，而 a[1] < a[2]，循环不执行。
• 当 i = 2 时，ans 从 1 增加到 2，循环执行一次。
• 此后每轮，ans 都从 i - 1 增加到 i，循环执行一次。

因此，外层 for 执行 \(n\) 次，里面的 while 总共只执行 \(n-1\) 次，加上读入和输出，总时间复杂度为 \[ O(n+n)=\boxed{O(n)}. \]

关键：嵌套循环不一定是 \(O(n^2)\)，要看内层循环累计执行了多少次。