Complejidad Computacional
El análisis de la complejidad computacional del algoritmo del Vecino Más Cercano se basa en contar el número de operaciones necesarias en función del número de nodos n del grafo.
-
Selección del nodo inicial: Se elige un nodo arbitrario como punto de partida. Esto se hace en tiempo constante:
O(1).
-
Búsqueda del nodo más cercano: En cada iteración se evalúan los nodos restantes para encontrar el más cercano. En la primera iteración se consideran n−1 nodos, luego n−2, y así sucesivamente.
-
Total de comparaciones: La suma total de comparaciones necesarias es:
(n−1) + (n−2) + ... + 1 = (n(n−1))/2
Esta suma es de orden cuadrático: O(n²).
-
Retorno al nodo inicial: Tras visitar todos los nodos, se regresa al punto de inicio con una operación adicional:
O(1).
Conclusión: La complejidad total del algoritmo se expresa como:
O(1) + O(n²) + O(1) = O(n²)
