含加法操作的嵌套循环时间复杂度求解咨询

先看你给出的代码：

for (let j = 2; j < N; j++) {
    for (let k = 2*j; k <= N; k += j) {
        do_sth;
    }
}

步骤1：计算单个外层循环对应的内层执行次数 #

对于每个j，内层循环的k从2j开始，每次加j，直到k <= N。我们可以把k写成m*j的形式，m从2开始，直到m*j <= N。最大的m就是Math.floor(N/j)，所以内层循环的执行次数是 Math.floor(N/j) - 1（减去m=1的情况，因为k从2j开始）。

步骤2：求和总执行次数 #

总操作次数就是把j从2到N-1的所有内层次数加起来，写成公式：
总次数 = Σ（j=2 到 j=N-1）[Math.floor(N/j) - 1]

把这个式子拆成两部分计算：

1. 第一部分：Σ（j=2到N-1）Math.floor(N/j)
   参考调和级数的性质：Σ（j=1到N）Math.floor(N/j) ≈ N * H_N，其中H_N是第N个调和数，近似等于lnN + γ（γ是欧拉常数，约0.577）。
   从j=2到N-1的求和，就是完整求和减去j=1和j=N的项：
   Σ（j=2到N-1）Math.floor(N/j) ≈ N*(lnN + γ) - N - 1

2. 第二部分：Σ（j=2到N-1）1
   这部分很直观，从j=2到N-1一共是N-2次，结果就是N-2。

步骤3：推导时间复杂度 #

把两部分结果合起来：
总次数 ≈ [N*(lnN + γ) - N - 1] - (N-2) = NlnN + (γ-2)N + 1

这里的主导项是NlnN，其他项都是O(N)级别的，相对于主导项可以忽略不计。而对数的底数不影响复杂度的阶，所以这段代码的时间复杂度是O(N log N)。

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