被 O 表示法困住了
我正在比较两种算法：Prim 算法和 Kruskal 算法。
我了解时间复杂度的基本概念，当两者效果最好时（稀疏/密集图），
我在互联网上找到了这个，但我正在努力将其转换为英语。
dense graph: Prim = O(N2)
Kruskal = O(N2*log(N))
sparse graph: Prim = O(N2)
Kruskal = O(N log(N))
这有点遥远，但有人能解释一下这里发生了什么吗？
I am comparing two algorithms, Prim's and Kruskal's.
I understand the basic concept of time complexity and when the two work best (sparse/dense graphs)
I found this on the Internet, but I am struggling to convert it to English.
dense graph: Prim = O(N2)
Kruskal = O(N2*log(N))
sparse graph: Prim = O(N2)
Kruskal = O(N log(N))
It's a bit of a long shot, but could anyone explain what is going on here?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
Prim 为 O(N^2)，其中 N 是顶点数。
Kruskal 是 O(E log E)，其中 E 是边数。 “E log E”来自于对边缘进行排序的良好算法。然后您可以在线性 E 时间内处理它。
在稠密图中，E ~ N^2。因此 Kruskal 的复杂度为 O( N^2 log N^2 )，即 O( N^2 log N )。
Prim is O(N^2), where N is the number of vertices.
Kruskal is O(E log E), where E is the number of edges. The "E log E" comes from a good algorithm sorting the edges. You can then process it in linear E time.
In a dense graph, E ~ N^2. So Kruskal would be O( N^2 log N^2 ), which is simply O( N^2 log N ).
好的，开始了。 O(N2)（2 = 平方）意味着大 N 的算法速度随着 N 的平方而变化 - 因此图大小的两倍将导致计算时间增加四倍。
Kruskal 行只是经过简化，并假设 E = c * N2。这里的 c 大概是一个常数，随着 N 变大，我们可以假设它显着小于 N。您需要了解以下对数定律：
log(ab) = log a + log b和log(a^n) = n * log a。这两者结合了 log c << 的事实。 log N（远小于并且可以忽略）应该让您理解那里的简化。现在，至于原始表达式以及它们的来源，您需要检查您从中获取这些表达式的页面。但我假设，如果你正在查看 Prim 和 Kruskal，那么你将能够理解其推导过程，或者至少，如果你不能理解，那么从长远来看，我向你解释它实际上不会对你有帮助...
OK, here goes. O(N2) (2 = squared) means that the speed of the algorithm for large N varies as the square of N - so twice the size of graph will result in four times the time to compute.
The Kruskal rows are merely simplified, and assume that
E = c * N2.chere is presumably a constant, that we can assume to be significantly smaller than N as N gets large. You need to know the following laws of logarithms:log(ab) = log a + log bandlog(a^n) = n * log a. These two combined with the fact that log c << log N (is much less than and can be ignored) should let you understand the simplifications there.Now, as for the original expressions and where they were derived from, you'd need to check the page you got these from. But I'm assuming that if you're looking at Prim's and Kruskal's then you will be able to understand the derivation, or at least that if you can't my explaining it to you is not actually going to help you in the long run...
Kruskal 对图中的边数 (E) 敏感，而不是节点数。
然而，Prim 仅受节点数量 (N) 的影响，计算结果为
O(N^2)。这意味着在边数接近 N^2（所有连接的节点）的密集图中，其复杂度因子
O(E*log(E))大致相当于O(N ^2*log(N))。c 是一个常数，用于说明“几乎”，并且与 O 表示法无关。 log(N^2) 与 log(N) 具有相同的数量级，因为对数大大超过 2 的幂 (
log(N^2) => 2*log(N)< /code> ，用 O 表示法是O(log(N))）。在稀疏图中，E 更接近 N，即
O(N*log(N))。Kruskal is sensitive to the number of edges (E) in a graph, not the number of nodes.
Prim however is only affected by the number of nodes (N), evaluting to
O(N^2).This means that in dense graphs where the number of edges approaches N^2 (all nodes connected) it's complexity factor of
O(E*log(E))is roughly equivalent toO(N^2*log(N)).The c is a constant to account for the 'almost' and is irrelevant in O notation. Also log(N^2) is of the same order of magnitude as log(N) as logarithm outweighs the power of 2 by a substantial margin (
log(N^2) => 2*log(N)which in O notation isO(log(N))).In a sparse graph E is closer to N giving you
O(N*log(N)).其思想是，在稠密图中，边的数量为 O(N^2)，而在稀疏图中，边的数量为 O(N)。因此，他们采用 O(E \lg E) 并用 E 的近似值对其进行扩展，以便将其直接与 Prim 的 O(N^2) 的运行时间进行比较。
基本上，它表明 Kruskal 更适合稀疏图，而 Prim 更适合密集图。
The thought is that in a dense graph, the number of edges is O(N^2) while in sparse graphs, the number of edges is O(N). So they're taking the O(E \lg E) and expanding it with this approximation of E in order to compare it directly to the running time of Prim's O(N^2).
Basically, it's showing that Kruskal's is better for sparse graphs and Prim's is better for dense graphs.
这两种算法都为不同的输入（节点和边）定义了 big-O。因此他们将一种转换为另一种以进行比较。
N 是图中的节点数 E 是边数。
对于稠密图，有 O(N^2) 条边；
对于稀疏图，有 O(N) 条边。
常数当然与 big-O 无关，因此 c 被排除
The two algorithms have big-O defined for different inputs (nodes and edges). So they are converting one to the other to compare them.
N is the number nodes in the graph E is the number of edges.
for a dense graph there are O(N^2) Edges
for a sparse graph there are O(N) Edges.
constants are of course irrelavent for big-O hence the c drops out
首先：n是顶点数。
Prim 是 O(n^2) 这部分很简单。
Kruskal 为 O(Elog(E))，其中 E 是边数。在稠密图中，有多达 N 个选择 2 条边，大约是 n^2 （实际上是 n(n-1)/2，但谁在数呢？）所以，大约是 n^2 log (n^2 ），即 2n^2 log n，即 O(n^2logn)，大于 O(n^2)
在稀疏图中，只有 n 个边，因此我们有 n log n，小于 O (n^2)。
First: n is the number of vertices.
Prim is O(n^2) that part is easy enough.
Kruskal is O(Elog(E)) where E is the number of edges. in a dense graph, there are as many as N choose 2 edges, which is roughly n^2 (actually it's n(n-1)/2, but who's counting?) so, it's roughly n^2 log (n^2) which is 2n^2 log n which is O(n^2logn) which is bigger than O(n^2)
In a sparse graph, there are as few as n edges, so we have n log n which is less than O(n^2).