Revisión de código

Revisa este código de un agente

Para un grafo de dependencias entre 2 millones de paquetes, un agente escribió:

Texto

1  dep ← matriz de V × V con ceros2  para cada (a, b) en dependencias:3      dep[a][b] ← 14  función dependencias_de(a):5      devolver todos los b con dep[a][b] = 1

Para un grafo de dependencias entre 2 millones de paquetes, un agente creó una matriz de V × V con ceros, puso un 1 en la casilla (a, b) por cada dependencia, y dependencias_de(a) devuelve todos los b con un 1 en la fila a. ¿Qué problemas tiene?Una matriz de 4 × 10¹² casillas para un grafo disperso, y recorrer 2 millones por paqueteLa matriz debería ser simétrica para ahorrar espacio, guardando solo la mitadDebería ser una matriz de bits: ocuparía 8 veces menos y cabría en la memoria disponibleNinguno: dependencias_de es O(V) y esa es la mejor cota posible para esta pregunta