求解嵌套循环代码的渐近复杂度（Θ表示）

嘿，我来帮你理清楚这个嵌套循环的渐近复杂度问题～先把你给出的代码整理一下，方便咱们分析：

void function(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j += i) {
            std::cout << "*";
        }
    }
}

首先你说得没错，外层循环确实会严格执行n次，关键就是搞清楚每次外层循环对应的内层循环执行次数，然后把所有次数加起来就行。

咱们逐个看外层的每个i：当i=1时，内层j从1开始每次加1，直到j<=n，这时候会跑n次；当i=2时，j每次加2，会跑⌊n/2⌋次；以此类推，对于任意一个i，内层循环的执行次数是⌊n/i⌋（向下取整，不过渐近分析里取整的影响可以忽略）。

所以总执行次数就是从i=1到n的⌊n/i⌋的和，也就是：
$$\sum_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor$$

你提到的调和级数其实找对方向啦！这个求和式可以近似为 $n \times \sum_{i=1}^{n} \frac{1}{i}$，而调和级数$\sum_{i=1}^{n} \frac{1}{i}$的渐近行为是$\Theta(\log n)$（简单说就是当n很大时，这个和大约等于$\ln n + \gamma$，其中$\gamma$是欧拉常数，是个固定值）。

那把n乘进去，总次数的渐近复杂度就是$\Theta(n \log n)$。

你之前疑惑的$\sum_{k=1}^n \frac{n(n+1)}{2}$其实是1到n的整数和，和咱们这个问题不相关；而你想到的调和级数正是关键，只要把它和n结合起来，就能得到最终的结果啦。

备注：内容来源于stack exchange，提问作者user14810275