nested-loops - 嵌套循环执行次数

Question

我永远无法理解如何计算嵌套循环中的内部循环被执行的次数。我想当我们有嵌套循环时，第一个循环的执行次数乘以第二个（内部）循环，但我发现他们使用 sigma 和 ... ex。

for i <- n − 1 down to 0 do
   for j <- 1 to i do
     if A[j − 1] > A[j] then
        swap(A[j], A[j − 1])

exact number of execution => (n-1)+(n-2)+...+1 = sigma[i=1 -> n-1] i = n(n-1)/2

对于这些循环，我总是试图写下发生了什么。例如对于这个我做了这样的：

i = 0 => j = - 
i = 1  => j = 1
.
.
.
i = n-1 => j = 1,2,3, ... , n-1

但后来我不知道该怎么办：/

我真的需要帮助谢谢

Answer 1

在您给出的示例中，内循环中的 j 取决于外循环中的 i (j<=i)。

你已经正确地列举了正在发生的处决。

你会得到：

1 + 2 + 3 + ... + n-1

这是一个高斯和。我们用来计算从 1 到 N 的连续数之和的公式是sum = N*(N+1)/2。

在这种情况下，N = n-1，因此总和（内循环运行的总数）将为：(n-1)*n/2。

我希望这能解决这个问题。

你一开始提到的案例：

我想当我们有嵌套循环时，第一个的执行次数乘以第二个（内部）一个

当内部循环不依赖于外部循环时为真（在这种情况下，如果 j 不依赖于 i）。