Cómo analizar la complejidad temporal del algoritmo MST de prims

Para analizar la complejidad del tiempo del algoritmo de Prim, he usado un montón binario en este caso.

MST-PRIM (G, w, r)
para cada u ∈ GV
u.key ← ∞
u.π ← NIL
r.key ← 0
Q ← GV
mientras que Q ≠ Ø
u ← EXTRACTO MIN (Q)
para cada v ∈ G.Adj [u]
si v ∈ Q yw (u, v) <v.key
v.π ← u
v.key ← w (u, v)

1. Aquí puede ver que, el tiempo requerido para una llamada a EXTRACT-MIN(Q) = O(log V) [usando la cola de prioridad mínima]. El ciclo while en la línea 6 está ejecutando V veces totales. Entonces EXTRACT-MIN(Q) se llama V veces. Entonces, el tiempo total requerido para EXTRACT-MIN(Q) = O(VlogV).
2. el bucle for en la line 8 se ejecuta 2E total veces (como la longitud total de todas las listas de adyacencia = 2E para el gráfico no dirigido). Tiempo requerido para ejecutar la línea 11=O(log v) [usando la operación DECREASE_KEY en el montón mínimo]. La línea 11 está ejecutando un total de 2E veces. Entonces, el tiempo total requerido para ejecutar la line 11=O(2Elog V) = O(Elog v).
3. El bucle for en la línea 1 se ejecutará por V veces. Usando el procedimiento BUILD_HEAP , para realizar las líneas 1 a 5, requerirá O(V) veces

Complejidad de tiempo total de MST-PRIM = tiempo requerido para ejecutar 1 + tiempo requerido para ejecutar 2 + tiempo requerido para ejecutar 3 =

• ¿Está roto el algoritmo de clasificación de Java y Python?
• ¿Cómo se resolvería el problema lingüístico 'Summer Eyes', de NACLO 2009?
• Puedo pensar en algoritmos en varias preguntas, pero cuando realmente escribo un código me enfrento a muchas dificultades. Entonces, siento que soy pobre escribiendo códigos. ¿Cómo puedo mejorar eso?
• Cómo ponerse al día con las matemáticas necesarias para poder comprender y analizar algoritmos si no sé sobre cosas como el registro
• ¿Son SHA256 y AES256 funciones hash o cifrados o algoritmos?

Total: O( VlogV + ElogV + V) = O(ElogV)

Espero que esto explique lo que necesitas saber.

¡Sigue codificando! 🙂