Was gilt als asymptotische Verbesserung für Graphalgorithmen?

Question

Nehmen wir an, wir versuchen, ein algorithmisches Problem zu lösen $A$ Das hängt von der Eingabe der Größe ab $n$.Wir sagen Algorithmus $B$ das läuft in der Zeit $T(n)$, ist asymptotisch besser als der Algorithmus $C$ was in der Zeit läuft $G(n)$ wenn wir haben:$G(n) = O(T(n))$, Aber $T(n)$ ist nicht $O(G(n))$.

Meine Frage bezieht sich auf die asymptotische Laufzeit von Graphalgorithmen, die normalerweise davon abhängt $|V|$ Und $|E|$.Insbesondere möchte ich mich auf den Algorithmus von Prim konzentrieren.Wenn wir die Prioritätswarteschlange mit einem binären Heap implementieren, wäre die Laufzeit $O(E\log V)$.Mit dem Fibonacci-Heap könnten wir eine Laufzeit von erreichen $O(V\log V + E)$.

Meine Frage ist, sagen wir das? $O(V\log V + E)$ ist asymptotisch besser als $O(E\log V)$?

Lassen Sie mich Folgendes klarstellen:Ich weiß, dass die Antwort „Ja“ lautet, wenn der Graph dicht ist.Aber falls $E=O(V)$ Beide Lösungen sind gleich.Mich interessiert mehr, was normalerweise ist definiert als asymptotische Verbesserung für den Fall, dass wir mehr als eine Variable haben, und noch schlimmer – die Variablen sind nicht unabhängig ($V-1\le E<V^2$, da wir für den Prim-Algorithmus davon ausgehen, dass der Graph zusammenhängend ist).

Danke!

Answer 1

Die freizügigste Definition lautet wie folgt.

Nehme an, dass $f(V,E),g(V,E)$ sind zwei Laufzeiten von Graphalgorithmen, die dasselbe Problem lösen.

Das sagen wir $f$ ist ein asymptotische Verbesserung in einigen Regimen An $g$ wenn es eine Sequenz gibt $V_n,E_n$ mit $V_n o \infty$ so dass$$ lim_ {n to inty} frac {f (v_n, e_n)} {g (v_n, e_n)} = 0.$$

Manchmal wird das Regime als uninteressant erachtet, aber das ist eine eher subjektive Angelegenheit.

Beachten Sie auch, dass sich das Problem bereits bei Funktionen mit einer Variablen manifestiert.In Betracht ziehen$$ f (n) = n^2, qquad g (n) = begin {cases} 2^n & text {if} n = 2^m, n & text {sonst}.end {Fälle} $$Ist $f$ eine asymptotische Verbesserung gegenüber $g$?Dies gilt für Eingaben mit einer bestimmten Länge, und das gilt auch für unsere obige freizügige Definition.