如何分析复杂程序的时间复杂度？附C++示例代码

先看给定的C++代码：

#include <iostream>
using namespace std;

int main() {
    int n, s = 0, i, j, k;

    cin >> n;

    for (i = 1; i <= n * n; i++) {
        for (j = 1; j <= i / 2; j++) {
            s += i + j;
        }

        k = 1;
        while (k < j) {
            s += k;
            k += 2;
        }
    }

    cout << s << endl;
    return 0;
}

步骤1：拆解各层循环执行次数 #

外层循环 #

外层循环变量i从1到n²，总共执行n²次。

内层for循环 #

内层for循环的终止条件是j <= i/2，对每个i，循环执行次数约为i/2（时间复杂度分析取渐近上界，忽略取整和常数细节）。

while循环 #

for循环结束后，j的最终值为floor(i/2) + 1。while循环中k从1开始每次加2，执行次数近似为j/2，代入j≈i/2后，次数约为i/4。

步骤2：计算总操作次数 #

对每个i，内层for循环+while循环的总操作次数约为i/2 + i/4 = 3i/4。

现在求和外层循环所有i的总操作次数，即计算：
$$\sum_{i=1}^{n²} \frac{3i}{4}$$

根据等差数列求和公式$\sum_{i=1}^{m} i = \frac{m(m+1)}{2}$，代入m = n²可得：
$$\frac{3}{4} \times \frac{n²(n² + 1)}{2} ≈ \frac{3}{8}n^4$$

步骤3：确定时间复杂度 #

忽略常数系数，取渐近上界，该程序的时间复杂度为O(n⁴)，确实远高于O(n²)。

内容的提问来源于stack exchange，提问作者Leon