O(V+E) 等于 O(V^2) 吗？
Is O(V+E) equivalent to O(V^2)?
我的问题是 O(V+E) = O(V^2).
基本上，如果 O(V+E) 是线性时间使得 V+E = n，那么 O(V^2) 不也是线性时间吗？
我假设 O(V+E) 的 worst-case/upper 边界是每个顶点之间的边，这将导致 (V-1)^2 边。我还假设可以考虑 V^2，所以我认为这相当于 O(V^2).
O(V + E) 的任何运行时也是 O(V2)，因为你阐明了 (E = O(V2))。不过，这并不意味着说运行时间为 O(V2) 是个好主意，因为这是一个不太精确的界限。在稀疏图中，O(V + E) 比 O(V2).
更紧
然而，反之则不然。例如，考虑这个算法：
for each node v in V:
for each node u in V:
print (v, u)
该算法的运行时间为 Θ(V2)，并且其运行时间不依赖于图中的边数。因此，说运行时间为 O(V + E) 是不正确的，因为在边数较少的图中（比如树），O(V + E) 的边界会错误地预测运行时间与节点数量呈线性关系，而 O(V2) 的运行时间将正确地 upper-bound 运行时间呈二次方。
如果您想为任何可以完全随机化的图调整大小，那么是的，您可以根据节点数计算最大边数。
你经常看到独立计算E和V的原因是现实。实际上完整的图并不常见。好吧，即使在理论上你也可以说你有 N 个节点的图，并且节点的平均边是某个常数，即 10.
例如，如果你想找到最快的路径，你可以为此实现 Dijsktra。如果你使用真实的道路并绘制整个世界的地图，将会有很多顶点，其中大部分将被限制为 4 条边（每个顶点都是十字路口，通常你在那里有 4 个选项），将会有更多的顶点，但不多，甚至是有限的（一个十字路口只能有有限数量的道路）。
因此，如果增加图的大小（顶点）不会增加节点的平均边数，则您需要独立计算 E 和 V 的信息。
例如现实世界中的 Dijkstra 具有线性复杂度。但是将 Dijsktra 用于任何图形都可能具有高达 V^2 的复杂性。但是如果你做的程序是在现实生活中寻找东西，你需要知道复杂度是线性的。
否，O (|V| + |E|)不等同于O (|V|^2)。
原因如下。
Basically, if O(V+E) is linear time such that V+E = n, wouldn't O(V^2) also be linear time?
也许这假设图形是以某种方式明确给出的，我们必须将其作为输入接收才能使用它，并且边的总输入大小为 O (|V| + |E|) = n.
但我们并不总是需要接收一次输入，然后运行一个算法一次。
在某些情况下，我们会多次收到输入图，然后 运行 算法，因此无论输入大小如何，我们都对其复杂性感兴趣。
在其他一些情况下，图形是隐式给出的，因此输入不会花费太多时间。
示例：考虑 k * k 棋盘上的 knight's graph：该图的顶点是棋盘正方形，边是马的走法。
要解决的一个示例问题是：给定两个正方形，找到它们之间的马的路径，这是移动次数最短的。
解决该问题的一个明显算法是 breadth-first search，它需要 O (|V| + |E|) 时间
（我们可以做得更好，但这不是重点。）
此处，输入的大小为O (1)：它只是棋盘的大小k，以及棋盘上两个正方形的坐标。
我们不必随时读取或显式构造图：它由大小 k 隐式给出。
在每个顶点中，我们可以在 O (1) 中枚举来自该顶点的所有（最多 8 条）边。
在k、|V| = O (k)、|E| <= 8 k等方面|E| = O (k)，所以我们也有O (|V| + |E|) = O (k)。
另一方面，O (|V|^2) = O (k^2) 比 O (k).
更宽松
因此，在此示例中，O (|V| + |E|) 与 O (|V|^2) 不同，因此它们通常不等价。
否
I assume the worst-case/upper bound for O(V+E) is an edge between each vertex, which would result in (V-1)^2 edges.
除非您的输入被特别限制为 simple graph，否则任何 non-simple 图都可以有多个连接成对顶点的边和连接到单个顶点的循环边。
想象一个非常简单的连接城镇周围环岛的道路系统：
- 回旋处由多条边连接（即一对相邻顶点），这些边可能是：
- 有向边（即可能匹配或不匹配且行进方向相反的道路）；和
- 无向边（即道路两侧的人行道 and/or 自行车道）
- 每个回旋处（顶点）也可以有自己关联的循环边：
- 有向边（环绕环岛的道路）；
- 无向边（人行道 and/or 自行车道从 subways/over 桥下穿过，从环形交叉路口辐射出去。
因此，即使对于这个简化的 real-world 示例，图形也不简单，并且有 multi-edges 和循环边，如果 O(|E|) = O(|V|³) 则 O(|V|+|E|) > O(|V|²)。
我的问题是 O(V+E) = O(V^2).
基本上，如果 O(V+E) 是线性时间使得 V+E = n，那么 O(V^2) 不也是线性时间吗？
我假设 O(V+E) 的 worst-case/upper 边界是每个顶点之间的边，这将导致 (V-1)^2 边。我还假设可以考虑 V^2，所以我认为这相当于 O(V^2).
O(V + E) 的任何运行时也是 O(V2)，因为你阐明了 (E = O(V2))。不过，这并不意味着说运行时间为 O(V2) 是个好主意，因为这是一个不太精确的界限。在稀疏图中，O(V + E) 比 O(V2).
更紧然而，反之则不然。例如，考虑这个算法：
for each node v in V:
for each node u in V:
print (v, u)
该算法的运行时间为 Θ(V2)，并且其运行时间不依赖于图中的边数。因此，说运行时间为 O(V + E) 是不正确的，因为在边数较少的图中（比如树），O(V + E) 的边界会错误地预测运行时间与节点数量呈线性关系，而 O(V2) 的运行时间将正确地 upper-bound 运行时间呈二次方。
如果您想为任何可以完全随机化的图调整大小，那么是的，您可以根据节点数计算最大边数。
你经常看到独立计算E和V的原因是现实。实际上完整的图并不常见。好吧，即使在理论上你也可以说你有 N 个节点的图，并且节点的平均边是某个常数，即 10.
例如，如果你想找到最快的路径，你可以为此实现 Dijsktra。如果你使用真实的道路并绘制整个世界的地图，将会有很多顶点，其中大部分将被限制为 4 条边（每个顶点都是十字路口，通常你在那里有 4 个选项），将会有更多的顶点，但不多，甚至是有限的（一个十字路口只能有有限数量的道路）。
因此，如果增加图的大小（顶点）不会增加节点的平均边数，则您需要独立计算 E 和 V 的信息。
例如现实世界中的 Dijkstra 具有线性复杂度。但是将 Dijsktra 用于任何图形都可能具有高达 V^2 的复杂性。但是如果你做的程序是在现实生活中寻找东西，你需要知道复杂度是线性的。
否，O (|V| + |E|)不等同于O (|V|^2)。
原因如下。
Basically, if O(V+E) is linear time such that V+E = n, wouldn't O(V^2) also be linear time?
也许这假设图形是以某种方式明确给出的，我们必须将其作为输入接收才能使用它，并且边的总输入大小为 O (|V| + |E|) = n.
但我们并不总是需要接收一次输入，然后运行一个算法一次。 在某些情况下，我们会多次收到输入图，然后 运行 算法，因此无论输入大小如何，我们都对其复杂性感兴趣。 在其他一些情况下，图形是隐式给出的，因此输入不会花费太多时间。
示例：考虑 k * k 棋盘上的 knight's graph：该图的顶点是棋盘正方形，边是马的走法。
要解决的一个示例问题是：给定两个正方形，找到它们之间的马的路径，这是移动次数最短的。
解决该问题的一个明显算法是 breadth-first search，它需要 O (|V| + |E|) 时间
（我们可以做得更好，但这不是重点。）
此处，输入的大小为O (1)：它只是棋盘的大小k，以及棋盘上两个正方形的坐标。
我们不必随时读取或显式构造图：它由大小 k 隐式给出。
在每个顶点中，我们可以在 O (1) 中枚举来自该顶点的所有（最多 8 条）边。
在k、|V| = O (k)、|E| <= 8 k等方面|E| = O (k)，所以我们也有O (|V| + |E|) = O (k)。
另一方面，O (|V|^2) = O (k^2) 比 O (k).
因此，在此示例中，O (|V| + |E|) 与 O (|V|^2) 不同，因此它们通常不等价。
否
I assume the worst-case/upper bound for O(V+E) is an edge between each vertex, which would result in (V-1)^2 edges.
除非您的输入被特别限制为 simple graph，否则任何 non-simple 图都可以有多个连接成对顶点的边和连接到单个顶点的循环边。
想象一个非常简单的连接城镇周围环岛的道路系统：
- 回旋处由多条边连接（即一对相邻顶点），这些边可能是：
- 有向边（即可能匹配或不匹配且行进方向相反的道路）；和
- 无向边（即道路两侧的人行道 and/or 自行车道）
- 每个回旋处（顶点）也可以有自己关联的循环边：
- 有向边（环绕环岛的道路）；
- 无向边（人行道 and/or 自行车道从 subways/over 桥下穿过，从环形交叉路口辐射出去。
因此，即使对于这个简化的 real-world 示例，图形也不简单，并且有 multi-edges 和循环边，如果 O(|E|) = O(|V|³) 则 O(|V|+|E|) > O(|V|²)。