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

Question

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

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

Добавление дополнительной вершины
- Продолжительность: V
- Пространство: V
Алгоритм Беллмана Форда по кратчайшему пути из одного источника
- Продолжительность: EV
- Пространство: V
Алгоритм кратчайшего пути всех пар Дейкстры
- Продолжительность: EV log V
- Пространство: V

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

O (V + EV + EV log V), которое упростится до O( EV log V)

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

Answer 1

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

С математической точки зрения, когда V стремится к очень большим числам, это меньше, чем EV, что меньше, чем EVlogV. Итак, для больших V сложность вашего алгоритма хорошо аппроксимируется EVlogV