Dijkstra算法（Lazy）运行时间分析

Question

我正在尝试计算 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)
            }
      }

Answer 1

首先，您可以将一些边界收紧一些并替换一些 $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|)$.

Answer 2

您的分析是正确的，但不紧。

而不是分别考虑while循环，而是单独考虑循环，最好将它们视为在一起。用于循环的内部主体为每个（顶点，对）边缘运行一次，总共 $ 2 | E | $ 时间。因此，所有放松操作的总运行时间只是<跨度类=“math-container”> $ o（| e | \ log | e | $ ）。

所有轮询操作的总运行时间也是 $ o（| e | \ log | e |）$ ，因为您也观察到，我们推断出来总运行时间为 $ o（| e | \ log | e |）$ 。