En una representación de lista de adyacencia de un grafo simple no dirigido G = (V, E), cada arista (u, v) tiene dos entradas en la lista de adyacencia: [v] en la lista de adyacencia de u, y [u] en la lista de adyacencia de v. Estos son llamados gemelos entre sí. Un puntero gemelo es un puntero de una entrada de lista de adyacencia a su gemelo. Si |E| = m y |V | = n, y el tamaño de la memoria no es una restricción, ¿cuál es la complejidad temporal del algoritmo más eficiente para establecer el puntero gemelo en cada entrada de cada lista de adyacencia?
(A) Θ(n 2 )
(B) Θ(m+n)
(C) Θ(m 2 )
(D) Θ(n 4 )
Respuesta: (B)
Explicación:Primero necesitas encontrar gemelos de cada Node. Puede hacer esto usando el recorrido de orden de nivel (es decir, BFS) una vez. La complejidad temporal de BFS es Θ(m +n).
Y debe usar la lista vinculada para la representación, que es espacio adicional (pero el tamaño de la memoria no es una restricción aquí).
Final, la complejidad del tiempo es Θ(m + n) para establecer un puntero gemelo.
La opción (B) es correcta.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA