带依赖关系的嵌套循环公式

Question

可能重复： Big O: Nested For Loop With Dependence

考虑到以下嵌套循环，我必须计算出它的大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

对于第一次迭代--内环n-1次为第二次-内环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)<=c.g(n)表示c>0 n0>0，这里n大于n0