Análisis del tiempo de ejecución del algoritmo Dijkstra (Lazy)

Question

Estoy intentando calcular el tiempo de ejecución de un algoritmo de Dijkstra.Todas las fuentes que he leído dicen que el tiempo de ejecución es O(E * log (E)) para una implementación diferida.

Pero cuando hacemos los cálculos obtenemos O(E * (Log(E)+E*Log(E))).

Como E no es una constante, no veo cómo alguien podría reducir esto a O(E * log (E).

¿Estamos analizando lo incorrecto o es posible reducirlo?

        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

En primer lugar, puedes ajustar un poco más algunos de los límites y reemplazar algunos $E$es con $v$s.El bucle while al principio sólo se ejecutará $O(|V|)$ iteraciones (visitas cada nodo solo una vez), y el for (Edge edge : graph.adj(min)) el bucle se ejecutará sólo $O(|V|)$ iteraciones como máximo (un nodo puede tener como máximo $O(|V|)$ bordes adyacentes).Lo mismo con los factores logarítmicos, aunque en ese caso no importa tanto ya que $O(\log |V|) = O(\log |E|)$ (si la gráfica es conexa).A través de una simple multiplicación esto te da $O(|V| \cdot (\log |V| + |V| \cdot \log |V|)) = O(|V|^2 \cdot \log |V|)$.En un gráfico denso, esta ya es la complejidad deseada.Dado que un gráfico denso tiene $O(|V|^2) = O(|E|)$.

Sin embargo, en un gráfico disperso, p.cuando $O(|E|) = O(|V|)$, entonces aún puedes hacerlo mucho mejor.

El problema al que se enfrenta es que multiplicar los límites superiores puede provocar una sobreestimación.Mira el siguiente ejemplo:

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

El bucle exterior corre claramente $O(N)$ veces, y el bucle interno también se ejecuta $O(N)$ veces (porque en el peor de los casos lo hace).Se puede decir que en total la complejidad es $O(N^2)$ veces.Pero esto es sólo un límite superior.

La mayoría de las veces, la función interna casi no funciona.En realidad, si cuentas el número de veces que ejecutas la función constant_work(), conseguirás$$N + 1 + 1 + \cdots + 1 = 2N - 1 = O(N)$$ $N$ iteraciones para i == 1 y de lo contrario solo $1$ iteración.Entonces el código se ejecuta $O(N)$ tiempo.

El mismo efecto ocurre cuando recorre los bordes al lado de un nodo: for (Edge edge : graph.adj(min)).Sí, en el peor de los casos tienes $O(|V|)$ bordes, pero en un gráfico disperso, la mayoría de las veces tienes mucho menos.

Puedes contarlos desde un ángulo diferente.Si fijas un borde $(u,v)$, ¿con qué frecuencia tocarás ese borde y te moverás hacia el cuerpo del bucle?¡Solo dos veces!Una vez cuando min == u, y una vez cuando min == v.Por lo tanto, la parte interna del bucle, con tiempo de ejecución. $O(\log |V|)$, se ejecutará sólo $O(2 |E|) = O(|E|)$ veces.Lo que significa que todo funciona $O(|E| \log |V|)$.

Answer 2

Su análisis es correcto, pero no apretado.

En lugar de considerar el bucle while y el bucle para por separado, es mejor considerarlos juntos.El cuerpo interno del bucle para el bucle de una vez para cada borde (vértice, par), para un total de $ 2 | e | $ veces.Por lo tanto, el tiempo total de funcionamiento de todas las operaciones de relajación es solo $ o (| e | \ log | e | $ ).

El tiempo total de funcionamiento de todas las operaciones de encuesta también es $ o (| e | \ log | e |) $ , como también observa, y deducimos esoEl tiempo total de funcionamiento es $ o (| e | \ log | e |) $ .