Почему алгоритм Дикстры работает в O (V + E log V) вместо O (V ^ 2)?

Question

Где V - количество вершин, а E - количество ребер, в худшем случае все узлы соединены, и на каждом узле вы просматриваете все остальные узлы. Так не будет ли это O(V ^ 2)? Я посмотрел его и обнаружил, что это на самом деле O(V + E log V), но без объяснения причин.

Answer 1

НЕТ, лучшая реализация Дейкстры с использованием кучи Фибоначчи в качестве очереди приоритета выполняется в O(|E|+|V|*log|V|) в соответствии с здесь . Имейте в виду, что в плотном графе, где |E| равно O(|v|^2), O(|E|+|V|*log|V|) становится равным O(|V|^2), где это наихудший случай алгоритма, но ни в одном из этих случаев он работает в O(|V|+|E|log|V|).

Answer 2

Ваш анализ не учитывает стоимость очереди с приоритетами. Тем не менее, вы не совсем ошибаетесь.

Требуется O (| E |) операций с клавишей уменьшения, так как почти каждое посещаемое вами ребро может сделать это, и O (| V |) операции удаления-минимума, так как вы должны сделать это, чтобы вытащить вершины из очереди.

Если вы используете кучу Фибоначчи в качестве приоритетной очереди, то ключ уменьшения занимает постоянное время, а delete-min - O (log | V | ) время, так что вы получите O (| E | + | V | log | V |). С точки зрения | V | только, | E | заменяется на O (| V | ² ), поскольку он может go такой высокий, и это доминирует над | V | журнал | V | термин, дающий общую сложность O (| V | ² ).

Таким образом, вы правы, если хотите дать оценку в терминах | V | только, но дает оценку в терминах | V | и | E | Отдельно предпочтительнее, потому что он передает больше информации . Он говорит вам, что он быстрее, чем O (| V | ² ) для разреженных графов, что может быть важно.

Обратите внимание, что O (V + E log V) вы искали предназначен для реализации, которая использует другой тип очереди приоритетов, например двоичную кучу, а не кучу Фибоначчи. Это часто встречается на практике.

Answer 3

Вы рассматриваете только ситуацию с полностью подключенным графом. нотация big-O для наихудшего случая задана определенными входными параметрами, и поскольку в данной сложности используются V и E, это означает, что полностью связанный граф не имеет значения. Для графов в целом алгоритм Дейкстры будет конечным sh на O (V + ElogV) или быстрее; для полностью связного графа, где E приблизительно (V ^ 2) / 2, он будет конечным sh в O (V ^ 2), что действительно быстрее, чем O (V + ((V ^ 2) / 2) logV) ).