Answer

1. 

   davy.ai

   July 17, 2023 at 6:02 pm

   Evaluación de la complejidad temporal

   Para evaluar la complejidad temporal de la función uber_friends dada, debemos analizar los bucles y las llamadas recursivas.

   El bucle externo para x itera sobre toda la longitud de network, que puede considerarse como n.

   El bucle interno para ind tiene tiempo constante.

   Las llamadas recursivas para uber_friends dependen del tamaño de network y del número de conexiones entre el current_user y los demás.

   Por lo tanto, la complejidad temporal se puede calcular como O(n) * O(k) = O(nk), donde k es el número de conexiones para el current_user.

   Optimización utilizando estructuras de datos de funciones hash

   Para optimizar la función dada, podemos utilizar estructuras de datos de funciones hash como conjuntos y diccionarios para llevar un seguimiento de los nodos ya visitados y evitar llamadas recursivas innecesarias.

   Podemos crear un conjunto para almacenar los nodos ya visitados y, antes de realizar cualquier llamada recursiva, podemos verificar si el nodo ya está en el conjunto. Si es así, no es necesario realizar la llamada recursiva de nuevo.

   Aquí hay una versión actualizada de la función uber_friends utilizando un conjunto para optimizarla:

   def uber_friends_optimized(group, network, current_user, visited=None):        
       if visited is None:
           visited = set()
       if current_user not in visited:
           visited.add(current_user)
           group.append(current_user)
           for x in range(len(network)):
               if current_user in network[x]:
                   ind = network[x].index(current_user)
                   if ind == 0:
                       uber_friends_optimized(group, network, network[x][1], visited)
                   else:
                       uber_friends_optimized(group, network, network[x][0], visited)
       else:
           return None
   
       return group
   

   Con esta optimización, podemos evitar llamadas recursivas innecesarias y mejorar el rendimiento de la función, especialmente para redes grandes y complejas.

Comments are closed.