Время выполнения алгоритма Дейкстры - приоритетная очередь (куча)

Question

Мне сложно понять, почему сложность алгоритма Дейкстры с кучей равна O ((m + n) * log (n)), где m - число ребер и n - число вершин.

Мое понимание:

Теперь я знаю, что нужно сделать, п ​​удалить мин. (Каждый снимок min берет log (n) из кучи).

Затем нужно сделать m обновить ключи. (Каждый ключ обновления принимает log (n)).

Отсюда и ответ. Является ли моя концепция понятной? В противном случае вы можете объяснить, как получить временную сложность Алгоритма Дейкстры.

Answer 1

Сложность немного меняется в зависимости от того, как вы используете Dijkstra с помощью кучи. Например, я использую встроенную очередь приоритетов в c++, и эта куча не поддерживает приоритетное обновление. Таким образом, каждый раз, когда я хочу обновить приоритет данного элемента, я просто нажимаю еще один элемент в куче. Это может привести к тому, что моя куча станет размером m (все же каждая вставка/поп имеет сложность O(log(m)), которая совпадает с O(log(n))).

Если вы используете кучу Фибоначчи, вы можете уменьшить сложность алгоритма.

Если вы используете обычную двоичную кучу, ваш анализ в значительной степени правильный - вам нужно нажать m элементов в куче, которая поддерживает вставку/поп в O(log(n)). Вам также необходимо удалить минимальный элемент как минимум n раз.