Понимание расчета сложности времени для алгоритма Дейкстры

Question

В соответствии с моим пониманием, я вычислил временную сложность алгоритма Дейкстры как обозначение большой O, используя приведенный ниже список смежности. Это не получилось так, как предполагалось, и это заставило меня понять это шаг за шагом.

1. Каждая вершина может быть подключен к (V-1) вершин, следовательно, число смежных ребер в каждой вершине V - 1. Допустим, Е представляет собой V-1 ребер, соединенных с каждой вершиной.
2. Поиск & Обновление веса каждой соседней вершины в куче min равно O (log (V)) + O (1) или O(log(V)).
3. Следовательно, из шагов 1 и 2 выше сложность времени для обновления всех смежных вершин вершины равна E * (logV). или E*logV.
4. Следовательно, временная сложность для всех V-вершин V * (E * logV) i.e O(VElogV).

Но сложность времени для алгоритма Дейкстры равна O (ElogV). Зачем?

Answer 1

кратчайшее алгоритм пути Дейкстры является O(ElogV) где:

• V это число вершин
• E общее число ребер

Ваш анализ правилен, но ваши символы имеют разные значения! Вы говорите, что алгоритм O(VElogV) где:

• V это число вершин
• E является максимальным числом ребер, прикрепленных к одному узлу.

Давайте переименуем ваш E в N. Поэтому один анализ говорит O(ElogV), а другой говорит O(VNlogV). Оба правильные и фактически E = O(VN). Разница в том, что ElogV - это более плотная оценка.