O que é considerado uma anī melhoria de algoritmos de grafos?

Question

Vamos dizer que estamos tentando resolver algum problema algorítmico $A$ que é dependente de entrada de tamanho $n$.Dizemos que o algoritmo de $B$ que é executado em tempo $T(n)$, é assintoticamente melhor do que o algoritmo de $C$ o que é executado em tempo $G(n)$ se, temos:$G(n) = O(T(n))$, mas $T(n)$ não é $O(G(n))$.

A minha questão está relacionada com a assintótico de tempo de execução de algoritmos de grafos, que é geralmente dependente $|V|$ e $|E|$.Especificamente pretende focar de Prim algoritmo.Se vamos implementar a fila de prioridade com um binário de pilha em tempo de execução seria $S(E\log V)$.Com heap de Fibonacci podem ter um tempo de execução de $O(V\log V + E)$.

A minha pergunta é, nós dizemos que $O(V\log V + E)$ é assintoticamente melhor do que $S(E\log V)$?

Deixe-me esclarecer:Eu sei que, se o gráfico é denso, a resposta é sim.Mas se $E=O(V)$ ambas as soluções são as mesmas.Eu estou mais interessado no que é geralmente definido como um assintótica de melhoria no caso de ter mais de uma variável, e, pior ainda - as variáveis não são independentes ($V-1\le E, desde que assumimos o gráfico é conectado para de Prim algoritmo).

Obrigado!

Answer 1

Mais permissiva definição é a seguinte.

Suponha que $f(V,E),g(V,E)$ são dois tempos de execução dos algoritmos de grafos resolver o mesmo problema.

Dizemos que $f$ é um assimptótico melhoria em alguns regime no $g$ se existe uma sequência de $V_n,E_n$ com $V_n o \infty$ de tal forma que $$ \lim_{n o\infty} \frac{f(V_n,E_n)}{g(V_n,E_n)} = 0.$$

Às vezes, o regime não é considerado interessante, mas que de uma forma mais questão subjetiva.

Note-se também que o problema já se manifesta para uma variável funções.Considere $$ f(n) = n^2, \qquad g(n) = \begin{cases} 2^n & ext{se } n = 2^m \\ n & ext{senão}.\end{cases} $$ É $f$ uma anī melhoria $g$?É para os insumos de um determinado comprimento, e de fato é assim que, sob a nossa permissivo definição acima.