algorithm - 具有依赖关系的嵌套循环公式

Question

可能重复：
大 O：嵌套的具有依赖关系的 For 循环

鉴于以下嵌套循环，我必须弄清楚它的大 O 复杂性：

for(i=0 to n)
    for(j=n-1;j>=i;j--)

我知道这将是复杂的O(n^2)，但我不确定如何找出内部循环的公式。

为了清楚起见，我写了一张表格：

n=10
i | j | outer iters | inner iters
0 | 9 |     1       |     10
1 | 9 |     2       |      9 
...
9 | 9 |    10       |      1

因此，外部循环运行n次数，而内部循环运行sum(n to n-9)。

有人告诉我答案是n(n-2)/2，我根本不知道如何从我所拥有的东西中得出这个结论。

协助将不胜感激。

Answer 1

观察每次外循环迭代执行内循环的次数。

When i=0, the inner loop has n iterations.
When i=1, the inner loop has n-1 iterations.
When i=2, the inner loop has n-2 iterations.
......
When i=k, the inner loop has n-k iterations.
.....
When i=n-2, the inner loop has 2 iterations.
When i=n-1, the inner loop has 1 iterations.

所以内循环的总迭代次数为1 + 2 + ... + (n-2) + (n-1) + n，等于n(n+1)/2。

Answer 2

将整数 1 到 n 相加是众所周知的高斯技巧：

_{（注意它是+ 1，不是- 2）}

建立直觉

这是一个直观的方法来了解为什么这个公式是正确的：

试着自己看看1 + 2 + 3 + 4 + 5 + 6

证明我们的直觉

但是，如果没有偶数个术语怎么办？它仍然有效吗？它适用于任意数量的术语吗？为了回答这个问题，我们最好证明我们的
假设：

用一个叫做数学归纳法的概念。
为此，我们首先需要建立一个基本情况，在这种情况下对于n = 1，这是非常正确的。

现在，对于归纳步​​骤。我们假设，我们已经为某些 证明了我们的假设n，基于这些知识，我们想证明它也适用于n + 1。如果这成功了，我们已经“神奇地”证明了所有自然数。为什么？我们已经证明它适用于n = 1，这n => n + 1一步意味着它现在被证明了n = 2，这意味着它也被证明了n = 3等等。这是一个多米诺骨牌效应，翻倒第一个会让所有其他人倒下（证明）。

在假设中替换n为n + 1我们的归纳步骤的结果。因此，我们已经证明了该公式对所有人都是正确的n。

Answer 3

第 1 次迭代 - 内循环 n-1 次 第 2 次迭代 - 内循环 n-2 次，依此类推

对于 n-1 次迭代 -- 内循环 1 次

总迭代次数 = (n-1)+(n-2)+..2+1 =n(n-1)/2

这是 n^2-n/2 这当然是 O(n^2) 因为我们可以把它写成 f(n)= n^2-n/2 和 g(n)=n^2

我们可以把它写成 0<=f(n)<=cg(n) for c>0 n0>0 这里 n 大于 n0