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

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

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

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(EV log V)

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


runtime algorithm big-o dijkstra bellman-ford
person Community    schedule 25.02.2014    source источник
comment
Граф хранится как список смежности или как матрица смежности?   -  person mbatchkarov    schedule 25.02.2014

Ответы (1)


arrow_upward
0
arrow_downward

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

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

person morepaolo    schedule 25.02.2014