complexity-theory - 如何计算这个循环的复杂度？

Question

这个循环的复杂度是多少？我无法绕过它。

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

}

Answer 1

O(n^3)， 我相信。请参阅方形金字塔数。

i循环有n迭代。

j循环：(1 + 2 + ... + n)，以n迭代开始，以 . 结束1。

k循环：(1² + 2² + ... n²)，j每次循环迭代的次数j。

最后：