Big o notazione dell'algoritmo composto da algoritmi più piccoli

Question

Sto lavorando su un assegnazione che richiede un grafico, aggiunge un vertice extra al grafico, applica Bellman Ford con il nuovo vertice come la sorgente, quindi utilizza le coppie di Dyjkstra tutte le coppie sul grafico.

Gli algoritmi utilizzati hanno i requisiti di scatto / spazio di spazio di:

Adding extra vertex
-- Running Time: V
-- Space: V
Bellman Ford single source shortest path algorithm
-- Running time: EV
-- Space: V
Dijkstra's all pairs shortest path algorithm
-- Running time: EV log V
-- Space: V

.

Ho difficoltà a capire se sto calcolando il grande o del processo totale.Ogni programma viene eseguito separatamente e l'uscita viene convogliata dal programma per il programma.Il mio però è l'algoritmo totale avrebbe un tempo di esecuzione Big-O di:

O (V + EV + EV LOG V) che si semplificherebbe a O (EV Log V)

Il requisito dello spazio sarebbe calcolato in modo simile.Sto pensando a questo correttamente?Grazie!

Answer 1

Esattamente, una "regola generale" è che, in una sequenza di blocchi di codice, la complessità complessiva è dominata dal blocco con la massima complessità (asintoticamente)

Matematicamente, quando V tende a numeri molto grandi, è più piccolo di EV, che è più piccolo di Evlogv.Quindi, per grande V, la complessità del tuo algoritmo è approssimata bene da evlogv