Dijkstra算法(Lazy)运行时间分析
-
29-09-2020 - |
题
我正在尝试计算 Dijkstra 算法的运行时间。我读过的所有资料都说,惰性实现的运行时间是 O(E * log (E)) 。
但是当我们进行数学计算时,我们得到 O(E * (Log(E)+E*Log(E)))。
由于 E 不是常数,我不知道如何将其简化为 O(E * log (E)。
我们分析的是错误还是可以减少?
while (!minPQ.isEmpty()) { <=== O(E)
Node min = minPQ.poll(); <=== O(log(e)
for (Edge edge : graph.adj(min)) { <=== O(E)
if (min.getId() == target.getId()) {
// Source and Target = Same edge
if (edgeTo.size() == 0) edgeTo.put(target, edge);
return;
}
relax(edge, min, vehicle); <=== log(e) (because of add method on PQ)
}
}
解决方案
首先,您可以将一些边界收紧一些并替换一些 $E$与 $V$s。最开始的while循环只会运行 $O(|V|)$ 迭代(每个节点只访问一次),并且 for (Edge edge : graph.adj(min))
循环只会运行 $O(|V|)$ 最多迭代(一个节点最多可以有 $O(|V|)$ 相邻的边缘)。与对数因子相同,尽管在这种情况下它并不那么重要,因为 $O(\log |V|) = O(\log |E|)$ (如果图形已连接)。通过简单的乘法可以得到 $O(|V| \cdot (\log |V| + |V| \cdot \log |V|)) = O(|V|^2 \cdot \log |V|)$。在密集图中,这已经是所需的复杂性。由于稠密图有 $O(|V|^2) = O(|E|)$.
然而在稀疏图中,例如什么时候 $O(|E|) = O(|V|)$, ,那么你还可以做得更好。
您面临的问题是乘以上限可能会导致高估。看下面的例子:
for (i = 1 to N) {
limit = N if i == 1 else 1
for (j = 1 to N) {
constant_work()
}
}
外循环明显运行 $O(N)$ 次,内循环也运行 $O(N)$ 次(因为在最坏的情况下确实如此)。你可以说总共的复杂度是 $O(N^2)$ 次。但这只是一个上限。
大多数时候,内部函数实际上几乎不做任何工作。实际上,如果您计算运行该函数的次数 constant_work()
, , 你会得到$$N + 1 + 1 + \cdots + 1 = 2N - 1 = O(N)$$
$N$ 迭代 i == 1
否则仅 $1$ 迭代。所以代码运行在 $O(N)$ 时间。
当您遍历节点旁边的边时,会发生相同的效果: for (Edge edge : graph.adj(min))
。是的,在最坏的情况下你有 $O(|V|)$ 边,但在稀疏图中,大多数时候你的边要少得多。
你可以从不同的角度来数它们。如果你固定一条边 $(u, v)$, ,您多久会触摸该边缘并进入循环体?只有两次!有一次当 min == u
, ,并且一次当 min == v
。因此循环的内部部分,以及运行时 $O(\log |V|)$, ,只会运行 $O(2 |E|) = O(|E|)$ 次。这意味着整个事情都在进行 $O(|E| \log |V|)$.
其他提示
您的分析是正确的,但不紧。
而不是分别考虑while循环,而是单独考虑循环,最好将它们视为在一起。用于循环的内部主体为每个(顶点,对)边缘运行一次,总共 $ 2 | E | $ 时间。因此,所有放松操作的总运行时间只是<跨度类=“math-container”> $ o(| e | \ log | e | $ )。
所有轮询操作的总运行时间也是 $ o(| e | \ log | e |)$ ,因为您也观察到,我们推断出来总运行时间为 $ o(| e | \ log | e |)$ 。