Большая O обозначение алгоритма, состоящего из небольших алгоритмов

Question

Я работаю над назначением, который принимает некоторый график, добавляет дополнительную вершину на график, применяет Bellman Ford с новой вершиной в качестве источника, то использует применение всех паров Dijkstra на графике.

Используемые алгоритмы имеют требования к пробелам / пространству:

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

.

У меня есть трудности, понимая, если я рассчитаю большой O об общем процессе.Каждая программа выполняется отдельно, и выходной вывод работает из программы в программу.Мой, хотя общий алгоритм будет иметь время выполнения Big-O:

o (v + ev + ev log v) , который будет упростить O (LOG V V)

Требование пространства будет рассчитано аналогичным образом.Я думаю об этом правильно?Спасибо!

Answer 1

Точно, «правильное правило» состоит в том, что в последовательности блоков кода общей сложности преобладают блок с наибольшей сложностью (асимптотически)

Матиматически, когда v стремится к очень большим числам, это меньше, чем эВ, что меньше, чем evlogv.Итак, для большого V, сложность вашего алгоритма хорошо аппроксимируется от Evlogv