Прим Алгоритм Сложность времени

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

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

Время = Θ (В) · 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), что значительно лучше.