GESP 八级 · GESP 202503 C++ 八级 第 15 题

下列程序实现了输出杨辉三角形，其时间复杂度为（ ）。

#include <iostream>
using namespace std;

#define N 35
int a[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        a[i] = 1;
        for (int j = i - 1; j > 0; j--)
            ________; // 在此处填入选项
        for (int j = 0; j <= i; j++)
            cout << a[j] << " ";
        cout << endl;
    }
    return 0;
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】递推｜空间优化

🎯 考纲定位 本题考查《GESP 八级大纲》算法模块中递推思想与空间优化技巧，命题人意在筛选出能识别“用一维数组模拟二维递推”的考生——这是区分八级与七级的核心分水岭。

🧠 解题思维 杨辉三角本质是递推：a[i][j]=a[i-1][j-1]+a[i-1][j]。但本题用一维数组 a[N]，必须倒序更新（j 从 i-1 到 1）：a[j]=a[j]+a[j-1]。这样外层循环 n 次，内层更新 j 次，总操作≈n²/2。因此时间复杂度 O(n²)。

🪤 陷阱拆解 错误选项源于对“每行更新次数”的误判：A 误以为每行 O(1)；B 混淆 O(n log n)；D 误判三重循环。最阴险的是倒序更新——若正序更新会覆盖尚未使用的 a[j-1]，导致数据错误。只背“杨辉三角 O(n²)”而不理解“为何要倒序”，就会选错。

🔄 反命题思维 若改为二维数组 a[35][35]，时间复杂度仍 O(n²)，但空间升至 O(n²)；若问“倒序更新的必要性”，答案变为“防止覆盖”。刷到类似题，先问自己“命题人想考我什么”——是递推公式、空间优化，还是复杂度计算。