Ce qui est considéré comme une asymptotique de l'amélioration pour les algorithmes de graphes?

Question

Disons que nous essayons de résoudre un problème algorithmique $A$ qui dépend d'entrée de taille $n$.Nous disons algorithme $B$ qui s'exécute dans le temps $T(n)$, est asymptotiquement mieux que l'algorithme de $C$ qui s'exécute dans le temps $G(n)$ si nous avons:$G(n) = O(T(n))$, mais $T(n)$ n'est pas $O(G(n))$.

Ma question est liée à la asymptotique temps d'exécution des algorithmes de graphes, qui est généralement fonction de $|V|$ et $|F|$.Plus précisément, je veux me concentrer sur l'algorithme de Prim.Si nous mettons en œuvre la file d'attente de priorité avec un tas binaire, le temps d'exécution serait $O(E\log V)$.Avec des tas de Fibonacci, nous pourrions obtenir un moment de l'exécution de $O(V\log V + E)$.

Ma question est nous dire que $O(V\log V + E)$ est asymptotiquement mieux que $O(E\log V)$?

Permettez-moi de clarifier:Je sais que si le graphe est dense, la réponse est oui.Mais si $E=O(V)$ les deux solutions sont les mêmes.Je suis plus intéressé à ce qui est généralement défini comme une asymptotique de l'amélioration dans le cas que nous avons plus d'une variable, et pire encore - les variables ne sont pas indépendantes ($V-1\le E, puisque nous supposons que le graphe est connecté à Prim de l'algorithme).

Merci!

Answer 1

Le plus permissif définition est la suivante.

Supposons que $f(V,E),g(V,E)$ sont deux temps d'exécution des algorithmes de graphes à résoudre le même problème.

Nous disons que $f$ est un asymptotique de l'amélioration dans certains régime sur $g$ s'il existe une séquence $V_n,E_n$ avec $V_n o \infty$ tels que $$ \lim_{n o\infty} \frac{f(V_n,E_n)}{g(V_n,E_n)} = 0.$$

Parfois, le régime n'est pas jugée intéressante, mais c'est plus subjectif.

Notez également que le problème déjà se manifeste pour des fonctions de la variable.Envisager $$ f(n) = n^2, \qquad g(n) = \begin{cas} 2^n & ext{si } n = 2^m, \\ n & ext{sinon}.\end{cas} $$ Est $f$ une asymptotique amélioration par rapport à $g$?C'est pour les entrées d'une certaine longueur, et est en effet sous nos permissive de la définition ci-dessus.