Analyse du temps d'exécution (Lazy) de l'algorithme de Dijkstra

Question

J'essaie de déterminer le temps d'exécution d'un algorithme de Dijkstra.Toutes les sources que j'ai lues disent que le temps d'exécution est O(E * log (E)) pour une implémentation paresseuse.

Mais lorsque nous faisons le calcul, nous obtenons O(E * (Log(E)+E*Log(E))).

Puisque E n'est pas une constante, je ne vois pas comment quelqu'un pourrait réduire cela à O(E * log (E).

Sommes-nous en train d’analyser le mal ou est-il possible de le réduire ?

        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

Tout d'abord, vous pouvez rendre certaines limites un peu plus strictes et remplacer certaines $E$s avec $V$s.La boucle while au début ne fonctionnera que $O(|V|)$ itérations (vous visitez chaque nœud une seule fois), et le for (Edge edge : graph.adj(min)) la boucle fonctionnera uniquement $O(|V|)$ itérations au maximum (un nœud peut avoir au plus $O(|V|)$ bords adjacents).Idem avec les facteurs logarithmiques, même si dans ce cas cela n'a pas autant d'importance puisque $O(\log |V|) = O(\log |E|)$ (si le graphique est connecté).Par simple multiplication cela vous donne $O(|V| \cdot (\log |V| + |V| \cdot \log |V|)) = O(|V|^2 \cdot \log |V|)$.Dans un graphe dense, c'est déjà la complexité souhaitée.Puisqu’un graphe dense a $O(|V|^2) = O(|E|)$.

Cependant, dans un graphique clairsemé, par ex.quand $O(|E|) = O(|V|)$, alors vous pouvez encore faire beaucoup mieux.

Le problème auquel vous êtes confronté est que multiplier les limites supérieures peut conduire à une surestimation.Regardez l'exemple suivant :

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

La boucle extérieure fonctionne clairement $O(N)$ fois, et la boucle interne s'exécute également $O(N)$ fois (car dans le pire des cas, c'est le cas).On peut dire qu'au total la complexité est $O(N^2)$ fois.Mais ce n’est qu’une limite supérieure.

La plupart du temps, la fonction interne ne fait pratiquement aucun travail.En réalité si vous comptez le nombre de fois que vous exécutez la fonction constant_work(), tu auras$$N + 1 + 1 + \cdots + 1 = 2N - 1 = O(N)$$ $N$ itérations pour i == 1 et sinon seulement $1$ itération.Donc le code s'exécute dans $O(N)$ temps.

Le même effet se produit lorsque vous effectuez une boucle sur les bords à côté d'un nœud : for (Edge edge : graph.adj(min)).Oui, dans le pire des cas, $O(|V|)$ bords, mais dans un graphique clairsemé, la plupart du temps vous en avez beaucoup moins.

Vous pouvez les compter sous un angle différent.Si vous fixez un bord $(u, v)$, à quelle fréquence allez-vous toucher ce bord et vous déplacer dans le corps de la boucle ?Seulement deux fois !Une fois quand min == u, et une fois quand min == v.Par conséquent, la partie interne de la boucle, avec le runtime $O(\log |V|)$, fonctionnera uniquement $O(2 |E|) = O(|E|)$ fois.Ce qui veut dire que tout se passe dans $O(|E| \log |V|)$.

Answer 2

Votre analyse est correcte, mais pas serrée.

Au lieu de considérer la boucle tandis que la boucle et la boucle de la boucle de la part, il vaut mieux les considérer ensemble.Le corps intérieur de la boucle de la boucle est une fois pour chaque bord (sommet, paire), pour un total de 2 $ | e | $ fois.Par conséquent, le temps d'exécution total de toutes les opérations de détente n'est que $ o (| e | \ log | e | $ ).

Le temps d'exécution total de toutes les opérations de sondage est également $ o (| e | \ log | e |) $ , comme vous l'observe également, et nous en déduisons queLe temps de fonctionnement total est $ o (| e | \ log | e |) $ .