Complejidad del tiempo del algoritmo de Prim

Question

Estaba buscando Wikipedia entry para el algoritmo de Prim y noté que su complejidad de tiempo con una matriz de adyacencia es O (V^2) y su complejidad de tiempo con una lista de montón y adyacencia es O (E lg (V)) donde E es el número de aristas y V es el número de vértices en el gráfico.

Como el algoritmo de Prim se usa en gráficos más densos, E puede acercarse a V^2, pero cuando lo hace, la complejidad de tiempo con un montón se convierte en O (V^2 lg (V)) que es mayor que O (V^2). Obviamente, un montón mejorará el rendimiento en lugar de buscar en el conjunto, pero la complejidad del tiempo dice lo contrario.

¿Cómo se desacelera el algoritmo con una mejora?

Answer 1

Aunque el montón le ahorra buscar a través de la matriz, ralentiza la parte de "actualización" del algoritmo: las actualizaciones de matriz son O (1), mientras que las actualizaciones de pila son O (log (N)).

En esencia, usted cambia la velocidad en una parte del algoritmo por velocidad en otra.

No importa qué, tendrá que buscar N veces. Sin embargo, en gráficos densos, necesitará actualizar mucho (~ V^2), y en gráficos dispersos, no lo hará.

Otro ejemplo en la parte superior de mi cabeza es la búsqueda de elementos en una matriz. Si solo lo hace una vez, la búsqueda lineal es la mejor, pero si hace muchas consultas, es mejor ordenarlas y usar búsquedas binarias todo el tiempo.

Answer 2

Creo que lo leyó mal hasta cierto punto. Para gráficos densos, el artículo habla sobre el uso de montones de Fibonacci con la complejidad de tiempo O (E + V log V), que es significativamente mejor.

Answer 3

Desde la Introducción a los algoritmos (Carmen)

Tiempo = Θ (V) · T (extracto-MIN) + Θ (E) · T (DISMINUCIÓN-KEY)

 
        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) 

Usar diferentes estructuras de datos causa diferentes complejidades de tiempo.