algorithm - 嵌套for循环的Big-O : Linear or Quadratic?

Question

我试图了解如何知道算法中的嵌套循环是否产生线性或二次 Big-Oh复杂。这是我想出的几个例子，但与蛮力循环和图遍历有关。我试着

我的思路是否正确？

示例 1:

N = ? // Number of elements in an array of integers
For i = 1 to N
    For j = 1 to N
        Print "foo"

• 复杂度: O(N^2)
• 为什么？ 因为我们有两个嵌套的 for 循环，它们将迭代相同的次数。因为我们在运行时不知道N的值，那么我们不得不说复杂度是O(N^2)？但是，如果我们硬编码 N=20，那么我们将有 O(N)？

示例 2:

N = ? // Number of elements in an array of integers
For i = 1 to log(N)
    For-each edge of log(N)
        Print "foo"

• 复杂度: O(log(N)^2)
• 为什么？ 因为我们有两个嵌套的 for 循环，它们将迭代相同的 log(N) 次。

示例 3:

V = ? // Total number of nodes in a graph
E = ? // Total number of edges in a graph (not of each iteration-node)
For i = 1 to V
    For j = 1 to E
        Print "foo"

• 复杂度: O(V*E)
• 为什么？ 因为我们不知道 V = E，所以我们不能说 O(V^2) 或 O(E^2)。我们不知道是 V>=E 还是 V<=E。所以我们只说 O(V*E) 来涵盖所有情况。

示例 4:

V = ? // Total number of nodes in a graph
For i = 1 to V
    For-each edge of V[i]
        Print "foo"

• 复杂度: O(|V| + |图中的边|)
• 为什么？ 因为我们知道|图中的边| != |V|，所以迭代次数不成正比。当图是有向图与无向图时，这重要吗？

Answer 1

Big-O 表示法描述了算法的运行时间如何随着输入的大小而变化。

在示例 1 中，如果您将 N 硬编码为 20，则输入不会缩放。该算法实际上变为 O(1)。

示例 2 与您对示例 1 的直觉相似，只是每个循环仅运行 log(n) 次迭代。

对于示例 3，我将其描述为在 O(mn) 时间内运行(m = 边数，n = 顶点数)，而不是 O(n^ 2)。

最后一个例子实际上比我最初认为的要微妙一些(谢谢，@Hurkyl!)。

边被顶点分割，所以除了运行外循环 |V| 之外，你还有效地运行了总共 2|E| 次内循环> 次。这导致您的算法复杂度为 O(|V| + 2|E|)。在大 O 表示法中常量通常被忽略，因此这被认为与 O(|V| + |E|) 相同。