Perché questo algoritmo funziona in O (n m)?

Question

Perché questo algoritmo funziona in O (n m)?

#1 da (3 voti)

1

Questo è da un post sul blog su Codeforces. Non riuscivo davvero a capire perché l'editorialista continui a sostenere che questo codice funziona in O ( n m )

Questo è un problema grafico, dove dovremmo trovare il numero di modi per attraversare da a a c. Nota che solo i percorsi come - > b - > c e a - > d - > c devono essere considerati. Cioè, ci dovrebbe essere una differenza di un solo nodo, tra di loro.

n è il numero di vertici, m è il numero di spigoli e nxt è l'elenco di adiacenze.

Let's iterate through all combinations of a and c just two simple nested loops in O(n^2) and find all candidates for b and d inside. To find candidates you can go through all neighbors of a and check that they are neighbors of c. Among all the candidates you should choose two junctions as b and d. So just use https://en.wikipedia.org/wiki/Combination All you need is to add to the answer , where r is the number of candidates (common neighbors of a and c). The code is:
for (int a = 0; a < n; a++)
    for (int c = 0; c < n; c++)
        if (a != c)
        {
            int r = 0;
            for (int b = 0; b < nxt[a].size(); b++)
                if (nxt[a][b] != a && nxt[a][b] != c && g[nxt[a][b]][c])
                    r++;
            result += r * (r - 1) / 2;
        }
It is easy to see that the total complexity is O(nm), because of sum of number of neighbors over all junctions is exactly m.

Se ci sono 3 loop coinvolti, allora come può la complessità del caso peggiore essere O ( n m )

c++ complexity graph

posta Dhruv Mullick 27.01.2015 - 09:43

fonte

1 risposta

Leggi altre domande sui tag c++ complexity graph

La gestione delle eccezioni appartiene al livello più basso del runtime? TDD e test di scrittura per l'elaborazione dei file

score 3 · Accepted Answer

Il ciclo esterno ha n iterazioni.

Il ciclo intermedio ha n iterazioni.

Il ciclo interno ha iterazioni deg ( a ). Questo perché l'array nxt è elenco di adiacenza del grafico, che significa nxt[a] è un elenco di tutti i bordi che vanno dal vertice a e quindi nxt[a].size() è (fuori) il grado di a .

Poiché m , il numero di spigoli, è Σ _a deg ( a ), i due interni i loop insieme rendono le m iterazioni e le volte in cui n è esterno.

Note : verifica se il margine da nxt[a][b] a c esiste O (1), perché g è matrice di incidenza. È un po 'insolito vedere sia la lista di adiacenza che le rappresentazioni del grafico di incidenza, perché entrambi devono essere preparati. L'approccio usuale consiste nell'utilizzare la lista di adiacenza per i grafici sparsi, cioè quelli con m ~ O ( n ), perché quindi deg (a) ~ O (1) e ricerca lineare nel per il margine di follow-up è costante-tempo, e utilizzare la matrice di incidenza per grafici densi, cioè quelli con m ~ O ( n ²), perché quindi O ( nm ) = O ( n ³) in ogni caso, quindi il loop su tutti i vertici invece che sui bordi in il ciclo interno non ha importanza.

L'altro problema è che l'autore di questo dovrebbe essere condannato per la scelta delle variabili. È usuale per gli algoritmi matematici utilizzare le variabili a lettera singola, ma almeno l'indice di indicazione variabile nell'elenco di adiacenza non deve essere preso dallo stesso intervallo delle variabili per i vertici. Utilizzerei u e v consueti per i vertici (ovvero u = a e v = c ) e i per l'indice (ovvero i = b ) .