Analyse der Laufzeit des Dijkstra-Algorithmus (Lazy).

Question

Ich versuche, die Laufzeit für einen Dijkstra-Algorithmus herauszufinden.Alle Quellen, die ich gelesen habe, besagen, dass die Laufzeit für eine verzögerte Implementierung O(E * log (E)) beträgt.

Aber wenn wir rechnen, erhalten wir O(E * (Log(E)+E*Log(E))).

Da E keine Konstante ist, sehe ich nicht, wie jemand dies auf O(E * log (E) reduzieren könnte.

Analysieren wir das Falsche oder ist eine Reduzierung möglich?

        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

Zunächst können Sie einige der Grenzen etwas enger machen und einige ersetzen $E$s mit $V$S.Die while-Schleife am Anfang wird nur ausgeführt $O(|V|)$ Iterationen (Sie besuchen jeden Knoten nur einmal) und die for (Edge edge : graph.adj(min)) Die Schleife wird nur ausgeführt $O(|V|)$ Iterationen höchstens (ein Knoten kann höchstens haben). $O(|V|)$ angrenzende Kanten).Das Gleiche gilt für die Log-Faktoren, obwohl es in diesem Fall seitdem nicht mehr so ​​wichtig ist $O(\log |V|) = O(\log |E|)$ (wenn der Graph zusammenhängend ist).Durch einfache Multiplikation erhält man das Ergebnis $O(|V| \cdot (\log |V| + |V| \cdot \log |V|)) = O(|V|^2 \cdot \log |V|)$.In einem dichten Diagramm ist dies bereits die gewünschte Komplexität.Da hat ein dichter Graph $O(|V|^2) = O(|E|)$.

In einem spärlichen Diagramm, z.Wann $O(|E|) = O(|V|)$, dann kann man es noch viel besser machen.

Das Problem, mit dem Sie konfrontiert sind, besteht darin, dass die Multiplikation der Obergrenzen zu einer Überschätzung führen kann.Schauen Sie sich das folgende Beispiel an:

for (i = 1 to N) {
    limit = N if i == 1 else 1
    for (j = 1 to N) {
        constant_work()
    }
}

Die äußere Schleife verläuft deutlich $O(N)$ mal, und die innere Schleife läuft auch $O(N)$ Mal (denn im schlimmsten Fall passiert es).Man kann sagen, dass die Komplexität insgesamt hoch ist $O(N^2)$ mal.Aber das ist nur eine Obergrenze.

Meistens leistet die innere Funktion tatsächlich fast keine Arbeit.In Wirklichkeit, wenn Sie zählen, wie oft Sie die Funktion ausführen constant_work(), Sie erhalten$$N + 1 + 1 + \cdots + 1 = 2N - 1 = O(N)$$ $N$ Iterationen für i == 1 und sonst nur $1$ Wiederholung.Der Code läuft also ein $O(N)$ Zeit.

Der gleiche Effekt tritt auf, wenn Sie Kanten neben einem Knoten durchlaufen: for (Edge edge : graph.adj(min)).Ja, im schlimmsten Fall schon $O(|V|)$ Kanten, aber in einem Diagramm mit geringer Dichte hat man meistens viel weniger.

Sie können sie aus einem anderen Blickwinkel zählen.Wenn Sie eine Kante fixieren $(u, v)$, wie oft berühren Sie diese Kante und bewegen sich in den Schleifenkörper hinein?Nur zweimal!Einmal als min == u, und einmal wann min == v.Daher der innere Teil der Schleife, mit Laufzeit $O(\log |V|)$, wird nur ausgeführt $O(2 |E|) = O(|E|)$ mal.Was bedeutet, dass das Ganze einläuft $O(|E| \log |V|)$.

Answer 2

Ihre Analyse ist korrekt, aber nicht fest.

Anstatt die While-Schleife und die für die Schleife separat zu berücksichtigen, ist es besser, sie zusammenzudenken.Der Innenkörper der für Loop läuft einmal für jede (Scheitel-, Paar-) Kante, für insgesamt $ 2 | E | $ Times.Daher ist die Gesamtlaufzeit aller Relaxoperationen nur $ O (| E | \ log | E | $ ).

Die Gesamtlaufzeit aller Abfragevorgänge ist auch $ O (| E | \ log | e |) $ , wie Sie auch beobachten, und wir schließen das abDie Gesamtlaufzeit ist $ O (| E | \ log | e |) $ .