Анализ временной сложности многоступенчатого графа с использованием динамического программирования снизу вверх

Question

Временная сложность многоступенчатого графа равна O (n ^ 2) или O (v ^ 2), но тогда некоторые люди говорят, что это O (E).Итак, от O (V ^ 2) до O (E) они берутся о плотных / полных графах, в которых число ребер | E |= | V ^ 2 |?

Answer 1

В алгоритме многоступенчатого графа для кратчайшего пути мы минимизируем стоимость каждого ребра ровно один раз.Таким образом, Сложность Времени составляет O(E).Однако в худшем случае мы получаем полный граф с ребрами E = n*(n-1)/2, поэтому наихудшая временная сложность становится O(E) = O(n^2).

Обратите внимание, что и в этом случае каждое ребро обрабатывается ровно один раз.