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

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

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

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

Ответ 1

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

V - количество вершин
E - общее число ребер

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

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

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

Ответ 2

пусть n будет количеством вершин, а m будет количеством ребер.

Поскольку с алгоритмом Дейкстры у вас есть O (n) delete-mins и O (m) lower_keys, каждая из которых стоит O (logn), общее время выполнения с использованием двоичных кучи будет O (log (n) (m + n)). Абсолютно возможно амортизировать стоимость уменьшения_ключа до O (1), используя кучи Фибоначчи, что приводит к общему времени выполнения O (nlogn + m), но на практике это часто не делается, поскольку штрафы за постоянные коэффициенты FH довольно велики и на случайных графах величина limit_keys намного ниже, чем его соответствующая верхняя граница (больше в диапазоне O (n * log (m/n)), что намного лучше на разреженных графах, где m = O (n)). всегда помните о том, что общее время выполнения зависит как от ваших структур данных, так и от класса ввода.

Ответ 3

На плотном (или полном) графике E logV > V^2

Использование связанных данных & двоичная куча не всегда лучше.

В этом случае я предпочитаю использовать только матричные данные и сохранять минимальную длину за строкой.

Просто V^2 нужно время.

В случае, E < V / logV.

Или максимальное число ребер на вершину меньше некоторой константы K.

Затем используйте двоичную кучу.