Алгоритм Беллмана-Форда Пространственная сложность

Я искал пространственную сложность алгоритма Беллмана-Форда, но в википедии Алгоритм Беллмана-Форда и говорит, что пространственная сложность равна O(V). на этой ссылке написано O(V^2) . Мой вопрос; какова истинная космическая сложность и почему?


algorithm bellman-ford graph-algorithm space-complexity
person F.Dindar    schedule 27.12.2016    source источник

Ответы (3)


arrow_upward
5
arrow_downward

Это зависит от того, как мы это определяем.

  1. Если предположить, что граф задан, дополнительная пространственная сложность равна O(V) (для массива расстояний).

  2. Если мы предположим, что граф также имеет значение, это может быть O(V^2) для матрицы смежности и O(V+E) для списка смежности.

Оба они в каком-то смысле «истинны». Это просто то, что мы хотим учитывать в конкретной задаче.

person kraskevich    schedule 27.12.2016
comment
Я думаю, что более вероятно, что разница в выходе. Список предшественников будет O(V), тогда как списки путей от источника к каждому из пунктов назначения будут O(V^2). В статье Википедии используется список предшественников, но я не знаком с упоминаемой библиотекой, поэтому не могу точно сказать, как форматируется их вывод. - person beaker; 27.12.2016

arrow_upward
2
arrow_downward

Есть два случая: -

  1. Если мы предположим, что граф задан, то нам нужно создать 2 массива (для массива расстояний и массива родителей), поэтому сложность дополнительного пространства составляет O(V) .

  2. Если мы также рассмотрим хранение графа, то:

    а) O (V ^ 2) для матрицы смежности

    б) O(V+E) для списка смежности

    c) O(E), если мы просто создадим список ребер, в котором будут храниться только все ребра

person Abhishek    schedule 02.03.2018

arrow_upward
-1
arrow_downward

Неважно, используем ли мы список смежности или.
матрицу смежности, если данный граф является полным, то

space complexity = input + extra
1  if we use adjacency matrix,  space = input + extra O(V^2)+O(V) ->Using min heap =O(V^2)
2 if we use adjacency list,  space = input + extraa 
In complite graph E = O(V^2)
O(V + E) + O(V) -> min heap = O(V^2)

Потому что, если мы говорим о пространственной сложности для алгоритма.
, мы всегда исходим из наихудшего случая, что может быть.
случается. В Дейкстре или Беллмане Форде оба имеют полный граф, пространственная сложность = O (V ^ 2)

person Vinod Chandani    schedule 14.07.2018