c++ - 三重嵌套 For 循环的时间复杂度，其中索引相互依赖

Question

我这里有类似 C++ 的伪代码:

 for ( i = 1; i ≤ (n – 2); i++)
     for (j = i + 1; j ≤ (n – 1); j ++)
         for (k = j + 1; k ≤ n; k++)
             Print “Hello World”;

我相当确定这个特定代码块的时间复杂度是 O(n^3) 因为它是三层嵌套的 for 循环并且它们都至少是 n - 2 所以我概括了 (n-2) * (n-1) * n

但我一直在尝试解决实际的时间复杂度函数。这是我走到了多远，无法继续:

从 i = 1 到 n-2 的求和，从 j = (i+1) 到 n-1 的求和，从 k = (j+1) 到 n 的求和。

我理解最里面的循环执行 n - (j+1) 步，中间循环执行 (n-1)-(i+1) 步，最外层循环执行 (n-2)-i 步.我只需要一些关于如何简化求和以得出时间复杂度函数的指示。

谢谢!

Answer 1

如果有兴趣，循环遍历一次取 3 个 n 个事物的每个组合，从 (1,2,3), (1,2,4), ... 开始，到 (n-2) ,n-1,n), 即 n!/(( 3!)( (n-3)!) ) = (n)(n-1)(n-2)/6 = (n^3 - 3n^2 + 2n)/6 ，这导致 O (n^3).