Análise do tempo de execução do algoritmo Dijkstra (preguiçoso)

Question

Estou tentando descobrir o tempo de execução de um algoritmo Dijkstra.Todas as fontes que li dizem que o tempo de execução é O(E * log (E)) para uma implementação lenta.

Mas quando fazemos as contas obtemos O(E * (Log(E)+E*Log(E))).

Como E não é uma constante, não vejo como alguém poderia reduzir isso para O(E * log (E).

Estamos analisando o errado ou é possível reduzir?

        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

Primeiro, você pode tornar alguns limites um pouco mais apertados e substituir alguns $E$está com $V$S.O loop while no início só será executado $O(|V|)$ iterações (você visita cada nó apenas uma vez) e o for (Edge edge : graph.adj(min)) o loop será executado apenas $O(|V|)$ no máximo iterações (um nó pode ter no máximo $O(|V|)$ bordas adjacentes).O mesmo acontece com os fatores logarítmicos, embora nesse caso não importe tanto, pois $O(\log |V|) = O(\log |E|)$ (se o gráfico estiver conectado).Através de uma multiplicação simples, isso lhe dá $O(|V| \cdot (\log |V| + |V| \cdot \log |V|)) = O(|V|^2 \cdot \log |V|)$.Num gráfico denso, esta já é a complexidade desejada.Como um gráfico denso tem $O(|V|^2) = O(|E|)$.

No entanto, em um gráfico esparso, por ex.quando $O(|E|) = O(|V|)$, então você ainda pode fazer muito melhor.

O problema que você está enfrentando é que multiplicar os limites superiores pode levar à superestimação.Veja o exemplo a seguir:

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

O loop externo funciona claramente $O(N)$ vezes, e o loop interno também é executado $O(N)$ vezes (porque na pior das hipóteses isso acontece).Você pode dizer que no total a complexidade é $O(N^2)$ vezes.Mas este é apenas um limite superior.

Na maioria das vezes, a função interna quase não funciona.Na realidade, se você contar o número de vezes que executa a função constant_work(), você vai ter$$N + 1 + 1 + \cdots + 1 = 2N - 1 = O(N)$$ $N$ iterações para i == 1 e caso contrário apenas $1$ iteração.Então o código é executado em $O(N)$ tempo.

O mesmo efeito acontece quando você faz um loop nas arestas próximas a um nó: for (Edge edge : graph.adj(min)).Sim, na pior das hipóteses você tem $O(|V|)$ arestas, mas em um gráfico esparso, na maioria das vezes você tem muito menos.

Você pode contá-los de um ângulo diferente.Se você fixar uma borda $(você, v)$, com que frequência você tocará essa borda e passará para o corpo do loop?Apenas duas vezes!Uma vez quando min == u, e uma vez quando min == v.Portanto a parte interna do loop, com tempo de execução $O(\log |V|)$, será executado apenas $O(2 |E|) = O(|E|)$ vezes.O que significa que a coisa toda funciona $O(|E| \log |V|)$.

Answer 2

Sua análise está correta, mas não rígida.

Em vez de considerar o loop while e o loop for separadamente, é melhor considerá-los juntos.O corpo interno do loop for é executado uma vez para cada aresta (vértice, par), para um total de $2|E|$ vezes.Portanto, o tempo total de execução de todas as operações de relaxamento é apenas $O(|E|\log |E|$).

O tempo total de execução de todas as operações de pesquisa também é $O(|E|\log |E|)$, como você também observa, e deduzimos que o tempo total de execução é $O(|E|\log |E|)$.