какова временная сложность Dijikstra с использованием минимальной двоичной кучи, но без функции обновления

Question

При использовании алгоритма Дейкстры для решения проблемы кратчайшего пути из одного источника, распространенным решением является использование двоичного minheap с операцией обновления. Консенсус для сложности времени O ((E + V) log (V)), потому что размер кучи ограничен V из-за доступности обновления, и есть операции E update и V extractMin как со сложностью logV.

Однако существуют также решения, которые просто добавляют новый узел приоритета / расстояния в очередь приоритетов, поскольку обновление очереди приоритетов отсутствует во многих языках, таких как c ++ и python. В этом сценарии размер кучи не постоянен в V. Какова временная сложность? Я предполагаю, что O (E log E), потому что каждый узел вставляется в приоритетную очередь на E раз, и в операции добавления может быть столько же записей E, сколько уже есть в очереди, поэтому сама операция добавления - это logE, в сочетании с E циклы, общая сложность O (ElogE).

Я прав в этом мышлении?

Answer 1

Это правильно. Я нашел хороший анализ здесь (прочитайте код C ++, обсуждение начинается с «Обратите внимание, что можно использовать встроенные кучи C ++ ...»).

Стоит отметить, что O (log E ) = O (log V ), потому что E <<em> V ² и, следовательно, log E <2 log <em>V . Таким образом, асимптотическая сложность времени не меняется. Сказав это, по моему опыту, код имеет тенденцию работать медленнее, потому что куча больше. С другой стороны, код короче и понятнее, потому что вам больше не нужна способность запускать decrease_key() и, следовательно, вам больше не нужны указатели в кучу для быстрого поиска узлов.