Sto iniziando a imparare la complessità del tempo, e ho cercato negli esempi la complessità temporale per qualche tipo semplice.Complessità del tempo dell'algoritmo del grafico depth-first
Volevo sapere come calcolare la complessità temporale media per una ricerca approfondita in un grafico con |V|=n e |E|=m, lasciare che il nodo di avvio sia 'u' e il nodo finale sia 'v'.
La complessità temporale per DFS è O (n + m). Otteniamo questa complessità considerando il fatto che stiamo visitando ogni nodo solo una volta e nel caso di un albero (senza cicli) stiamo attraversando tutti i bordi una volta.
Ad esempio, se il nodo iniziale è u, e il nodo finale è v, stiamo pensando allo scenario peggiore quando v sarà l'ultimo nodo visitato. Quindi stiamo iniziando a visitare ciascun componente del primo vicino di te, quindi il componente connesso del secondo vicino, e così via fino al componente connesso dell'ultimo vicino, dove troviamo v. Abbiamo visitato ogni nodo solo una volta, e non ha attraversato lo stesso bordo più di una volta.
rispettato signore, Sono nuovo per l'analisi della complessità, in realtà sto facendo un progetto sul sistema operativo, sto cercando di trovare i cicli nel grafico di allocazione delle risorse ... io sono trovare i cicli usando una modifica della profondità prima ricerca .. sto cercando di confrontare la complessità di questo algoritmo con l'algoritmo del banchiere..possiamo dare la derivazione matematica di "avergae case performance" – Learner
"Prestazione media del caso" è il valore atteso (cioè un termine dalla teoria della probabilità) del tempo di esecuzione su una presunta distribuzione di probabilità di input. –
sarà O (n + m) se il grafico è dato sotto forma di lista di adiacenza ma se il grafico è in forma di matrice di adiacenza allora la complessità è O (n * n), come attraversare l'intera fila fino a trovare un margine.
So che questo è troppo tardi .. Ma per altri che potrebbero venire a cercare, ecco un'analisi dettagliata. http://techieme.in/depth-first-traversal – dharam