所以我正在学习一些图算法,现在是克鲁斯卡尔算法,了解到建议使用并查集来检查添加边是否会创建环,只需要花费O(Log V)的时间。对于实际目的,我理解为什么要这样做,但是严格按照大O符号来看,这样做实际上会影响最坏情况下的复杂度吗?
我的推理:如果我们不使用并查集,而使用DFS来检查循环,那么运行时间将为O(E+V),您必须执行V次才能获得O(V^2 + VE)的运行时间。虽然比使用并查集的O(V * LogV)更多,但Kruskal的主要复杂性来自于从优先队列E中删除最小元素,其答案为O(E * logE),即大O答案。我也没有看到空间优势,因为并查集需要O(V)空间,而使用DFS找到循环所需的数据结构也需要O(V)空间。
对于一个可能过于冗长的问题的简单回答:在Kruskal算法中使用并查集实际上会影响最坏情况下的运行时间吗?
我的推理:如果我们不使用并查集,而使用DFS来检查循环,那么运行时间将为O(E+V),您必须执行V次才能获得O(V^2 + VE)的运行时间。虽然比使用并查集的O(V * LogV)更多,但Kruskal的主要复杂性来自于从优先队列E中删除最小元素,其答案为O(E * logE),即大O答案。我也没有看到空间优势,因为并查集需要O(V)空间,而使用DFS找到循环所需的数据结构也需要O(V)空间。
对于一个可能过于冗长的问题的简单回答:在Kruskal算法中使用并查集实际上会影响最坏情况下的运行时间吗?