Время выполнения для алгоритма Dijkstra на приоритетной очереди реализовано отсортированным списком/массивом
Таким образом, мне любопытно знать то, что время выполнения для алгоритма идет на приоритетной очереди, реализованной отсортированным списком/массивом. Я знаю для неотсортированного списка/массива, это - O ((n^2+m)), где n является количеством вершин и m количество краев. Таким образом это приравнивает к O (n^2) время. Но это было бы быстрее, если бы я использовал отсортированный список/массив... Каково время выполнения было бы? Я знаю, что extractmin был бы постоянным временем.
1 ответ
Что ж, давайте рассмотрим, что нам нужно для алгоритма Дейкстры (для справок в будущем обычно вершины и ребра используются как V и E, например O (VlogE)):
Объединение всех отсортированных Списки смежности: O (E)
Извлечь минимум: O (1)
Ключ уменьшения: O (V)
Дейкстра использует O (V ) извлекает минимум операций, а O (E) уменьшает ключевые операции, поэтому:
O (1) * O (V) = O (V)
O (E) * O (V) = O (EV) = O (V ^ 2)
Взяв наиболее асимптотически значимую часть:
Конечная асимптотическая продолжительность выполнения равна O (V ^ 2) .
Можно ли это улучшить? да. Изучите двоичные кучи и лучшие реализации приоритетных очередей.
Edit : Я действительно сделал ошибку, теперь, когда я смотрю на это снова. E не может быть больше, чем V ^ 2, или, другими словами, E = O (V ^ 2).
Следовательно, в худшем случае алгоритм, который, как мы пришли к заключению, работает в O (EV), на самом деле будет O (V ^ 2 * V) == O (V ^ 3)