for循环的运行时，其中变量取决于外部循环

Question

我在理解嵌套for循环的运行时有些问题。我明白了：

for(int x=0; x<10; x++) // runs 10 times
for(int y=0; y<n; y++) // runs n times

for(int i=0; i<n; i++)
    for(int j=0; j<n; j++) // runs n*n = n^2 times

但是，当这些变量相互链接时，我感到困惑。例如：

for(int i=0; i < N; i++) // runs n times
    for(int j=i+1; j<N; j++) // runs n*n times but 1 time less every pass?
        for(int k=j+1; k<N; k++) // ???

您能通过简单的说明来指出正确的方向，以解决此问题吗？

Answer 1

仅对于第二个示例中的i和j循环，计数为（N-1）+（N-2）+ ... + 3 + 2 + 1，可以显示为等于N（N-1）/ 2。

Answer 2

受Scott的回答启发...

更一般而言，该公式是用于计算二项式系数的乘法公式（其中，n是上方的N，k是嵌套循环的数量（3）：]]]

(n(n-1)(n-2)…(n-(k-1))) / k!
继续阅读：

二项式系数：https://en.wikipedia.org/wiki/Binomial_coefficient

下降阶乘幂：https://en.wikipedia.org/wiki/Falling_and_rising_factorials

对于特定分析：https://math.stackexchange.com/questions/2202061/calculating-the-number-of-iterations-in-a-variable-number-of-nested-for-loops