Мне трудно понять, почему сложность алгоритма Дейкстры с кучей составляет O ((m + n) * log (n)), где m - количество ребер, а n - количество вершин.
Насколько я понимаю:
Теперь я знаю, что нужно удалить минуты. (Каждое удаление min берет log (n) из кучи).
Затем нужно сделать m ключей обновления. (Каждый ключ обновления занимает log (n)).
Отсюда и ответ. Ясна ли моя концепция? В противном случае не могли бы вы объяснить, как получить временную сложность алгоритма Дейкстры.
Сложность незначительно варьируется в зависимости от способа реализации Дейкстры с использованием кучи. Например, я использую встроенную очередь приоритетов в c++, и эта куча не поддерживает обновление приоритета. Таким образом, каждый раз, когда я хочу обновить приоритет данного элемента, я просто помещаю еще один элемент в кучу. Это может привести к тому, что моя куча станет размером m (все же каждая вставка / всплывающая подсказка имеет сложность O(log(m)), что совпадает с O(log(n))).
Если вы используете кучу Фибоначчи, вы можете уменьшить сложность алгоритма.
Если вы используете обычную двоичную кучу, ваш анализ в значительной степени верен - вам нужно поместить m элементов в кучу, которая поддерживает вставку / извлечение в O(log(n)). Вам также необходимо удалить минимальный элемент не менее n раз.
