大 O 复杂性中的嵌套 for 循环

Question

for(int i = 0; i < n; i++) {
    for(int j = 0; j < i; j++){
        // do swap stuff, constant time
    }
}

我读到单个 for 循环是 O(N)，遍历它两次将使它成为 O(n^2)。

看了相关教程，每个操作都以1为单位 - O(1)。我想详细了解 O(n^2) 是如何出现的。我尝试对每条语句进行数学计算，但我相信我做的不对。如果有人能真正向我展示嵌套 for 循环如何变成 O(n^2)，我将不胜感激。预先感谢

Answer 1

从 i = 1 循环到 n 然后有一个从 1 到 i 的内部循环的函数将经历等于此公式的迭代次数：

n(n+1)/2

如您所见，当我们去掉除主指数以外的所有内容时，您以 O(n^2)

结束

Answer 2

你需要运用古老而晦涩的数学艺术，计算出内部语句的执行次数。

在你的例子中，内部循环执行了 i 次。 i 的值为 0、1、2、...、n-1。所以你需要一个计算这个总和的公式，这就是你的结果。

你读到单循环是O(n)。那是胡说八道。这取决于循环。

for (i = 1; i < n; i *= n)

不迭代n次。它迭代 log2 (n) 次，这通常要少得多。您需要查看实际代码并弄清楚。对此没有简单的规则。

Answer 3

如你所说

Each takes unit of 1 - O(1)

所以内循环的每次迭代需要1,2,3,...,n个单位时间。

total_time = 1 +   2   +   3   + ... + (n-2) + (n-1) + n

反转

total_time = n + (n-1) + (n-2) + ... +   3   +   2   + 1

添加

2 * total_time = (n+1) + (n+1) + (n+1) + ... + (n+1) + (n+1) + (n+1)

共有n项

2 * total_time = (n+1) * n

=> total_time = (n+1) * n / 2

=> total_time = n^2 / 2 + n / 2

对于大 O 复杂度，忽略了低项和常数系数。

结果

O(n^2)

Answer 4

for(int i = 0; i < n; i++){  // outer loop
    for(int j = 0; j < i; j++){  // inner loop
        //do swap stuff, constant time
    }
}

在外循环的第一次迭代中（i = 0），内循环不执行。

在外循环的第二次迭代中（i = 1），内循环执行once.

外循环第三次迭代（i=2），内循环执行twice.

所以，在外循环的最后一次迭代中（i = n），内循环执行n times.

因此，这段代码执行的总次数是

1 + 2 + 3 + … + n

= n(n + 1) / 2（自然数求和公式）

= ((n^2) + n) / 2

= O(n^2)

————————

另外，看看这些

Nested for loop in Big Oh Complexity