<分区>
Possible Duplicate:
Big O: Nested For Loop With Dependence
鉴于以下嵌套循环，我必须弄清楚它的 Big 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，但我根本不知道如何从我所拥有的信息中得出这个结论。
如有帮助，我们将不胜感激。
最佳答案
观察外循环每次迭代的内循环执行次数。
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。
关于algorithm - 具有依赖性的嵌套循环的公式，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12568416/