嵌套 for 循环的大 O：线性还是二次？

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 表示法描述了算法的运行ning 时间如何随着输入的大小而变化。

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

示例 2 类似于您对示例 1 的直觉，除了每个循环只有运行s log(n) 次迭代。

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

最后一个例子实际上比我最初给予它的信任稍微细微一些（谢谢，@Hurkyl！）。

边被顶点分割，所以除了运行外循环 |V| 次。这导致您的算法复杂度为 O(|V| + 2|E|)。常量在 big-o 表示法中通常被忽略，因此这被认为与 O(|V| + |E|).

相同

嵌套 for 循环的大 O：线性还是二次？

Big-O of Nested-for-loops: Linear or Quadratic?

algorithm

big-o

time-complexity

nested-loops

asymptotic-complexity