В соответствии с моим пониманием, я вычислил временную сложность алгоритма Дейкстры как запись большого О с использованием приведенного ниже списка смежности. Это не получилось так, как предполагалось, и это заставило меня понять это шаг за шагом.
O(log(V)).E*logV.O(VElogV).Но временная сложность алгоритма Дейкстры равна O (ElogV). Почему?
Алгоритм кратчайшего пути Дейкстры O(ElogV) где:
V - количество вершинE - общее число реберВаш анализ верен, но ваши символы имеют разные значения! Вы говорите, что алгоритм O(VElogV) где:
V - количество вершинE - максимальное количество ребер, связанных с одним node.Переименуйте E в N. Таким образом, один анализ говорит O(ElogV), а другой говорит O(VNlogV). Оба правильны и фактически E = O(VN). Разница в том, что ElogV является более строгой оценкой.
пусть 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)). всегда помните о том, что общее время выполнения зависит как от ваших структур данных, так и от класса ввода.
На плотном (или полном) графике E logV > V^2
Использование связанных данных & двоичная куча не всегда лучше.
В этом случае я предпочитаю использовать только матричные данные и сохранять минимальную длину за строкой.
Просто V^2 нужно время.
В случае, E < V / logV.
Или максимальное число ребер на вершину меньше некоторой константы K.
Затем используйте двоичную кучу.