Сложность алгоритма Прима

Question

Я искал Wikipedia entry для алгоритма Прима, и я заметил, что его временная сложность с матрицей смежности равна 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

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

Answer 3

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

Время = Θ (V) · Т (ЭКСТРАКТ-МИН) + Θ (Е) · Т (УМЕНЬШИТЬ-КЛЮЧ)

 
        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) 

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