Analisi dell'algoritmo di Dijkstra (pigro) Tempo di esecuzione

Question

Sto cercando di capire il tempo di correzione per un algoritmo di DigiTra.Tutte le fonti che ho letto dicono che il tempo di esecuzione è o (e * log (e)) per un'implementazione pigra.

Ma quando facciamo la matematica otteniamo o (e * (log (e) + e * log (e))).

Dal momento che E non è una costante, non vedo come qualcuno potrebbe ridurlo a O (E * Log (E).

stiamo analizzando il torto o è possibile ridurre?

        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

Prima di, puoi fare alcuni dei limiti un po 'più stretti e sostituire alcuni $ e $ s con $ v $ s. Il ciclo mentre all'inizio eseguirà solo $ o (| v |) $ iterazioni (visitate ogni nodo una sola volta) e il ciclo for (Edge edge : graph.adj(min)) eseguirà solo $ o (| v |) $ iterazioni al massimo (un nodo può avere al massimo $ o (| v |) $ bordi adiacenti). Lo stesso con i fattori di registro, anche se in tal caso non importa tanto da $ o (\ log | v |)= o (\ log | e |) $ (Se il grafico è collegato). Tramite semplice moltiplicazione Questo ti dà $ o (| v | \ clot (\ log | v | + | v | \ cdot \ log | v |))= o (| v | ^ 2 \ cdot \ log | v |) $ . In un grafico denso, questa è già la complessità desiderata. Dal momento che un grafico denso ha $ o (| v | ^ 2)= o (| e |) $ .

comunque in un grafico sparso, ad es. Quando $ o (| e |)= o (| v |) $ , quindi puoi comunque fare molto meglio.

Il problema che stai affrontando è che moltiplicando i limiti superiori può portare alla sovrastimazione. Guarda il seguente esempio:

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

.

Il ciclo esterno funziona chiaramente $ o (n) $ volte, e il loop interno funziona anche $ o (n ) $ volte (perché nel peggiore dei casi lo fa). Puoi dire che in totale la complessità è $ o (n ^ 2) $ volte. Ma questo è solo un limite superiore.

La maggior parte del tempo la funzione interiore effettivamente non funziona quasi. In realtà Se si conta il numero di volte in cui esegui la funzione constant_work(), otterrai $$ n + 1 + 1 + \ Cdots + 1= 2N - 1= o (n) $$ $ N $ Iterazioni per i == 1 e altrimenti solo $ 1 $ Iterazione. Quindi il codice viene eseguito in $ o (n) $ tempo.

Lo stesso effetto avviene quando si attiva i bordi accanto a un nodo: for (Edge edge : graph.adj(min)). Sì, nel peggiore dei casi che hai $ o (| v |) $ bordi, ma in un grafico sparse, la maggior parte delle volte che hai molto meno. .

Puoi contareli da un angolo diverso. Se si fissa un bordo $ (u, v) $ , quanto spesso toccherai quel bordo e spostati nel corpo del loop? Solo due volte! Una volta quando min == u, e una volta quando min == v. Pertanto la parte interna del ciclo, con runtime $ o (\ log | v |) $ , eseguirà solo $ o (2 | e |)= o (| e |) $ volte. Il che significa che l'intera cosa corre in $ o (| e | \ log | v |) $ .

Answer 2

La tua analisi è corretta, ma non stretta.

Invece di considerare il ciclo mentre il ciclo e il loop separatamente, è meglio considerarli insieme.Il corpo interno del ciclo per correre una volta per ogni bordo (vertice, coppia), per un totale di $ 2 | e | $ volte.Pertanto, il tempo totale di funzionamento di tutte le operazioni di relax è solo $ o (| e | \ log | e | $ ).

Il tempo di funzionamento totale di tutte le operazioni di sondaggio è anche $ o (| e | \ log | e |) $ , mentre osservi anche questoIl tempo di esecuzione totale è $ o (| e | \ log | e |) $ .