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

Question

我对这篇 SO 帖子有疑问: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 帖子中的比较不同，我如何生成或提出这个公式？

Answer 1

您必须训练自己的思维来识别并遵循执行中的模式，并针对特定情况提出公式。一般的经验法则是，如果一个 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)次。