algorithm - 这个嵌套的三重 for 循环的复杂性是什么？

Question

我在 StackOverflow 上搜索了一下，了解了 j 循环点的复杂性，即 O(n<sup>2</sup>) .然而，随着 k 循环的嵌套添加，我很困惑为什么复杂性变成了 O(n<sup>3</sup>)。 .有人可以帮助我理解这一点吗？

据我了解，i 循环有 n 次迭代，j 循环有 1+2+3+...+n 次迭代 n*(n+1)/2这是 O(n<sup>2</sup>) .

for(i = 1; i < n; i++) {   
    for(j = i+1; j <= n; j++) {
        for(k = i; k <= j; k++) {
           // Do something here...
        }
    }
}

编辑: 感谢大家的帮助 :) Balthazar，我写了一段代码，它会根据计数器所处的循环递增计数器，这是一种粗略的循序渐进方式-步骤:

#include <iostream>

int main(int argc, const char * argv[])
{
    int n = 9;
    int index_I = 0;
    int index_J = 0;
    int index_K = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            for (int k = i; k <= j; k++) {
                index_K++;
            }
            index_J++;
        }
        index_I++;
    }
    std::cout << index_I << std::endl;
    std::cout << index_J << std::endl;
    std::cout << index_K << std::endl;
    return 0;
}

我以 1 为增量从 n=2 运行这段代码到 n=9，得到以下序列:

因此从计数器可以看出:i = n-1 给出 O(n) 的复杂度，j = ((n-1)*n)/2 给出复杂度 O(n<sup>2</sup>) .很难发现 K 的模式，但已知 K 取决于 J，因此:

k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6给出复杂度 O(n<sup>3</sup>)

我希望这对 future 的人们有所帮助。

EDIT2:谢谢Dukeling对于格式:) 还发现最后一行有错误，现在更正

Answer 1

如果您习惯了 Sigma 表示法，这里有一个正式的方法来推断您的算法的时间复杂度(准确地说是简单的嵌套循环):

注意:公式简化可能包含错误。如果您发现任何问题，请告诉我。