Lo que se considera un asintótica mejora de algoritmos de gráfico?

Question

Digamos que estamos tratando de resolver algún problema algorítmico $A$ que depende de la aportación de tamaño $n$.Decimos que el algoritmo de $B$ que se ejecuta en el tiempo $T(n)$, es asintóticamente mejor que el algoritmo de $C$ que se ejecuta en el tiempo $G(n)$ si tenemos:$G(n) = O(T(n))$, pero $T(n)$ no es $O(G(n))$.

Mi pregunta está relacionada con la asintótica en el tiempo de ejecución de algoritmos de gráfico, que es por lo general depende de $|V|$ y $|E|$.Específicamente quiero centrarme en el algoritmo de Prim.Si aplicamos la cola de prioridad binario con un montón de tiempo de ejecución sería $O(E\log V)$.Con Fibonacci montón podríamos obtener un tiempo de ejecución de $O(V\log V + E)$.

Mi pregunta es: ¿podemos decir que $O(V\log V + E)$ es asintóticamente mejor que $O(E\log V)$?

Permítanme aclarar:Sé que si la gráfica es más densa que la respuesta es sí.Pero si $E=O(V)$ ambas soluciones son las mismas.Estoy más interesado en lo que se suele definido como un asintótica de mejora en el caso de que tenemos más de una variable, y peor aún - las variables no son independientes ($V-1\le E, ya que asumimos que el gráfico está conectado por el algoritmo de Prim).

Gracias!

Answer 1

La definición más permisiva es la siguiente.

Supongamos que $ f (v, e), g (v, e) $ son dos tiempos de ejecución de algoritmos de gráficos que resolven el mismo problema.

Decimos que $ f $ es una mejora asintótica en algún régimen en $ g $ Si existe una secuencia $ v_n, e_n $ con $ v_n \ to \ infty $ tal que $$ \ lim_ {n \ to \ infty} \ frac {f (v_n, e_n)} {g (v_n, e_n)}= 0. $$

A veces el régimen no se considera interesante, pero eso es un asunto más subjetivo.

Tenga en cuenta también que el problema ya se manifiesta para funciones de una variable. Considerar $$ f (n)= n ^ 2, \ qquad g (n)=comienzan {casos} 2 ^ n \ texto {if} n= 2 ^ m, \\n& \ texto {lo contrario}. \ End {casos} $$ Es $ f $ una mejora asintótica sobre $ g $ ? Es para las entradas de cierta longitud, y de hecho está tan bajo nuestra definición permisiva anterior.