Временная сложность алгоритма Прима

Question

Я смотрел на Запись в Википедии для алгоритма Прима и я заметил, что его временная сложность с матрицей смежности равна O (V ^ 2), а его временная сложность с кучей и списком смежности равна O(E lg (V)), где E - количество ребер, а V - количество вершин в графе.

Поскольку алгоритм Прима используется в более плотных графах, E может приближаться к V ^ 2, но когда это происходит, временная сложность с кучей становится O (V ^ 2 lg (V)), что больше, чем O (V ^ 2).Очевидно, что куча повысит производительность по сравнению с простым поиском по массиву, но временная сложность говорит об обратном.

Как на самом деле алгоритм замедляется при улучшении?

Answer 1

Несмотря на то, что куча избавляет вас от поиска по массиву, это замедляет "обновляющую" часть алгоритма:обновления массива равны O(1), в то время как обновления кучи равны O(log(N)).

По сути, вы обмениваете скорость в одной части алгоритма на скорость в другой.

Несмотря ни на что, вам придется выполнить поиск N раз.Однако в плотных графиках вам нужно будет много обновлять (~ V ^ 2), а в разреженных графиках вы этого не делаете.

Другой пример, который приходит мне в голову, - это поиск элементов в массиве.Если вы делаете это только один раз, линейный поиск является лучшим, но если вы выполняете много запросов, лучше сортировать их и использовать бинарный поиск каждый раз.

Answer 2

Из введения в алгоритмы (Кармен)

Время = Θ (V)· T (ВЫДЕРЖКА-МИН) + Θ(E)· T(КЛАВИША УМЕНЬШЕНИЯ)

                   T(EXTRACT-MIN)   T(DECREASE-KEY)   Total

1. array            O(V)             O(1)              O(V^2)
2. binary heap      O(lgV)           O(lgV)            O(E lgV)
3. Fibonacci heap   O(lgV)           O(1)              O(E + VlgV)

Использование разных структур данных приводит к разным временным сложностям.

Answer 3

Я думаю, что вы в какой-то степени прочитали это неправильно.Для плотных графиков в статье говорится об использовании куч Фибоначчи с временной сложностью O (E + V log V), что значительно лучше.