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。

そして最後に：