c# - 各种嵌套for循环的算法时间复杂度

关于这篇文章我有个问题:Understanding How Many Times Nested Loops Will Run
其中3个嵌套for循环的一般公式为:n(n+1)(n+2)/3。我真的不知道为什么第二个内环运行N + 1倍,而外循环运行N次(内环不会再次运行之前,它退出了for循环)?不管怎样…一般公式是

n(n+1)(n+2)...(n+r-1)
---------------------
         r!

这里,r是嵌套循环的数目。
我想知道这个公式对于嵌套循环是否总是相同的,或者它是否基于for循环中的比较而改变……如果它基于比较,那么如果在考试中我得到了一些不同的for循环,我如何确定公式如果for循环的比较与创建该公式的SO post中的比较不同,我如何生成或提出该公式?

最佳答案

你必须训练你的思维去识别和遵循执行中的模式,并为特定的情况想出一个公式。一般经验法则是,如果一个for循环将在其内部运行代码x次,并且其中有一个循环将在其内部运行y次,那么内部循环中的代码将运行x*y次。
最常见的for循环类型从零开始,递增1,直到达到某个数字,如下所示:

for(int i = 0; i < x; i++)
    for(int j = 0; j < y; j++)
        for(int k = 0; k < z; k++)
            // code here runs x * y * z times

为了回答您的问题,如果您更改任何 for循环的任何部分,它将更改内部代码的执行次数。您需要通过考虑逻辑代码的执行来确定要执行多少次。
for(int i = 1; i < x; i++)
    for(int j = 0; j < y * 2; j++)
        for(int k = 0; k < z; k += 2)
            // code here runs (x - 1) * (y * 2) * (z / 2) times

在上面的示例中,每个 for循环都以不同的方式进行调整。请注意,运行次数的总体公式几乎保持不变,但现在每个循环每次被命中时运行的次数都不同。
当循环的变量影响多个循环时,事情变得更加复杂。
for(int i = 0; i < x; i++)
    for(int j = i; j < y; j++) // notice how `j` starts as `i`
        // Code here runs `y` times the first time through the outer loop,
        // then `y - 1` times,
        // then `y - 2` times,
        // ...
        // if x < y, the pattern continues until the xth time,
        // when this loop runs `y - x` times.
        // if x > y, the pattern will stop when y == x, and
        // code here will run 0 times for the remainder of
        // the loops.

所以在最后一个例子中,假设 x < y,循环将运行 y + (y-1) + (y-2) ... + (y-x)次。