CSP-S 2019 第一轮 第21题：最坏情况下，此程序的时间复杂度是（

题目

#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;
}

最坏情况下，此程序的时间复杂度是（）。

选项

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

答案

A

题解

选 A. \(O(n^2)\)。

关键在于：ans 会被重置为 i，所以它可能反复扫描同一段数组，不能认为整个程序中 ans 最多增加 \(n\) 次。

考虑数组交替出现： ``text 2 1 2 1 2 1 ... 2 1 ``

• i = 1 时，a[i] = 2，所有元素都不大于它，ans 一直增加到 n。
• i = 2 时，发生下降，ans 被重置为 2。下一个元素是 2，while 不执行。
• i = 3 时，a[i] = 2，ans 又从 2 一直增加到 n。
• i = 4 时，ans 又被重置为 4。
• 后面不断重复这个过程。

因此，while 的总执行次数约为： \[ n+(n-2)+(n-4)+\cdots=\Theta(n^2). \]

外层循环执行 \(n\) 次，每次内层最多执行 \(n\) 次，上界也是 \(O(n^2)\)。所以最坏时间复杂度为 \(O(n^2)\)。