PUERTA | Puerta TI 2005 | Pregunta 15

En la siguiente tabla, la columna de la izquierda contiene los nombres de los algoritmos gráficos estándar y la columna de la derecha contiene las complejidades temporales de los algoritmos. Relaciona cada algoritmo con su complejidad temporal.

1. Algoritmo de Bellman-Ford 2. Algoritmo de Kruskal 3. Algoritmo de Floyd-Warshall 4. Clasificación topológica

A : O (m log n) B : O (n 3 ) C : O (nm) D : O (n + m)

 
(A) 1→ C, 2 → A, 3 → B, 4 → D
(B) 1→ B, 2 → D, 3 → C, 4 → A
(C) 1→ C, 2 → D, 3 → A , 4 → B
(D) 1→ B, 2 → A, 3 → C, 4 → D

Respuesta: (A)
Explicación:

• Algoritmo Bellman-Ford : Complejidad temporal: O(VE)
• Algoritmo de Kruskal : Complejidad del tiempo: O(ElogE) o O(ElogV). La clasificación de los bordes requiere un tiempo O(ELogE). Después de ordenar, iteramos a través de todos los bordes y aplicamos el algoritmo de búsqueda de unión. Las operaciones de búsqueda y unión pueden tomar como máximo un tiempo O(LogV). Entonces, la complejidad general es O (ELogE + ELogV) tiempo. El valor de E puede ser como máximo V ^ 2, por lo que O (LogV) son O (LogE) iguales. Por lo tanto, la complejidad temporal total es O(ElogE) u O(ElogV)
•  Algoritmo de Floyd-Warshall :  Complejidad de tiempo : O (V ^ 3)
•  Clasificación topológica :  Complejidad de tiempo: el algoritmo anterior es simplemente DFS con una pila adicional. Entonces, la complejidad del tiempo es la misma que DFS, que es O (V + E).

Cuestionario de esta pregunta