如何计算这两段C++程序的时间复杂度？

第一段程序 #

for(i = 0; i < N; i++)
        for(j = 0; j < i * i; j++)
            for(k = 0; k < j; k ++)
                sum ++;

时间复杂度验证 #

你算出的O(n^5)是正确的，推导过程如下：

• 最外层循环执行N次（i从0到N-1）。
• 对每个i，中间层循环执行约i²次（j从0到i²-1）。
• 对每个j，最内层循环执行约j次（k从0到j-1）。

总执行次数为嵌套求和：
$$\sum_{i=0}^{N-1} \sum_{j=0}^{i2-1} j$$

先计算内层求和：$\sum_{j=0}^{i2-1} j = \frac{i²⁽ⁱ2 - 1)}{2} \approx \frac{i^4}{2}$（大N场景下低阶项可忽略）。
再对外层求和：$\sum_{i=0}^{N-1} \frac{i^4}{2} \approx \frac{1}{2} \sum_{i=1}^{N-1} i^{4$，而自然数四次方的求和渐近增长阶为O(n}5)，因此该程序时间复杂度为O(n^5)。

第二段程序 #

for(i = 1; i < N; i++)
    for(j = 1; j < i * i; j++) 
            if(j %i == 0)
            for(k = 0; k < j; k++)

时间复杂度验证 #

你得出的O(n^{3)结论有误，正确时间复杂度为O(n}4)，推导过程如下：

• 最外层循环执行N-1次（i从1到N-1）。
• 中间层循环中，仅当j是i的倍数时才会触发内层循环。j的范围是1到i²-1，符合条件的j为i、2i、...、(i-1)i，共i-1个值。
• 对每个符合条件的j=ki（k从1到i-1），内层循环执行ki次。

总执行次数为嵌套求和：
$$\sum_{i=1}^{N-1} \sum_{k=1}^{i-1} ki$$

先计算内层求和：$\sum_{k=1}^{i-1} ki = i \cdot \frac{(i-1)i}{2} \approx \frac{i^3}{2}$（大N场景下低阶项可忽略）。
再对外层求和：$\sum_{i=1}^{N-1} \frac{i^3}{2} \approx \frac{1}{2} \sum_{i=1}^{N-1} i^{3$，而自然数三次方的求和渐近增长阶为O(n}4)，因此该程序时间复杂度为O(n^4)。

内容的提问来源于stack exchange，提问作者我从上边来