如何确定嵌套循环的时间复杂度？

Question

我知道第一个循环是 O(n)，因为第二个是嵌套循环，所以它将是 O(n * something)。我知道嵌套循环将迭代 n 次并每次递减。但是如何确定它的时间复杂度？

int a = 0;
for (i = 0; i < N; i++) {
    for (j = N; j > i; j--) {
        a = a + i + j;
    }
}

Answer 1

我假设你的意思是渐近时间复杂度。

内部循环将运行 N-i 次，其主体为 O(1)。

展开外层循环，复杂度为O(N) + O(N-1).... + O(1)，总和为O(N^2)。

Answer 2

从技术上讲，该算法的时间复杂度或指令数运行的顺序为：

Sum(N-i) for i=0 to i=N

由于内循环每次运行N次运行ning而已。每次迭代运行ning 1 count less.

扩展后的总和如下所示：

N + N - 1 + N - 2 + .... 2, 1, 0

等同于：

Sum (i) For i = 0 to i = N

这又可以解决为：

n(n-1)/2 ==> n^2/2 + n/2

和

O(0.5*n^2 + 0.5 n) is effectively O(n^2)

How to determine the time complexity of the nested loop?