Big O Notación de algoritmo compuesto por algoritmos más pequeños

Question

Estoy trabajando en una asignación que toma un poco de gráfica, agrega un vértice adicional al gráfico, aplica Bellman Ford con el nuevo vértice como la fuente, luego utiliza los pares de Dijkstra a la gráfica.

Los algoritmos que se están utilizando tienen requisitos de tiempo de ejecución / espacio de:

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

Estoy teniendo dificultades para entender si estoy calculando la gran O del proceso total.Cada programa se ejecuta por separado, y la salida se canaliza del programa al programa.Aunque es el algoritmo total tendría un tiempo de ejecución de BIG-O de:

o (V + EV + EV Log V) que simplificaría a o (EV LOG V)

El requisito de espacio se calculará de manera similar.Estoy pensando en esto correctamente?¡Gracias!

Answer 1

Exactamente, una "regla de pulgar" es que, en una secuencia de bloques de código, la complejidad general está dominada por el bloque con mayor complejidad (asintóticamente)

Matemáticamente, cuando V tiende a números muy grandes, es más pequeño que EV, lo cual es más pequeño que Evlogv.Entonces, para gran V, la complejidad de su algoritmo se aproxima bien por EVLOGV