En esta sección, vamos a poner en práctica los conceptos de optimización de algoritmos que hemos aprendido en los módulos anteriores. Realizaremos ejercicios que nos permitirán mejorar el rendimiento del código, tanto en términos de tiempo como de espacio. Cada ejercicio incluirá una descripción del problema, un ejemplo de código inicial, y una serie de pasos para optimizarlo. Al final de cada ejercicio, se proporcionará una solución optimizada y una explicación detallada de las mejoras realizadas.
Ejercicio 1: Optimización de Búsqueda Lineal
Descripción del Problema
Dado un array de números enteros, queremos encontrar si un número específico está presente en el array. El enfoque inicial es utilizar una búsqueda lineal.
Código Inicial
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return True
return False
# Ejemplo de uso
arr = [1, 3, 5, 7, 9, 11]
target = 7
print(linear_search(arr, target)) # Output: TruePasos para Optimizar
- Mejora de la Condición de Salida: Podemos mejorar la eficiencia del bucle añadiendo una condición de salida temprana.
- Uso de Estructuras de Datos Adecuadas: Convertir el array en un conjunto (
set) para aprovechar la búsqueda en tiempo constante.
Código Optimizado
def linear_search_optimized(arr, target):
return target in set(arr)
# Ejemplo de uso
arr = [1, 3, 5, 7, 9, 11]
target = 7
print(linear_search_optimized(arr, target)) # Output: TrueExplicación de la Optimización
- Condición de Salida Temprana: En el código inicial, el bucle continúa hasta el final del array incluso si el elemento se encuentra antes. La optimización con
setpermite realizar la búsqueda en tiempo constante O(1).
Ejercicio 2: Optimización de Ordenamiento por Burbuja
Descripción del Problema
El algoritmo de ordenamiento por burbuja es ineficiente para grandes listas. Vamos a optimizarlo para mejorar su rendimiento.
Código Inicial
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# Ejemplo de uso
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr)) # Output: [11, 12, 22, 25, 34, 64, 90]Pasos para Optimizar
- Detección de Lista Ordenada: Añadir una bandera para detectar si la lista ya está ordenada y evitar iteraciones innecesarias.
- Optimización de Bucle Interno: Reducir el número de comparaciones en cada iteración.
Código Optimizado
def bubble_sort_optimized(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
return arr
# Ejemplo de uso
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort_optimized(arr)) # Output: [11, 12, 22, 25, 34, 64, 90]Explicación de la Optimización
- Detección de Lista Ordenada: La bandera
swappedpermite salir del bucle si no se realizaron intercambios en una iteración, indicando que la lista ya está ordenada. - Reducción de Comparaciones: El bucle interno se reduce en cada iteración, ya que los elementos más grandes se "burbujearán" hacia el final de la lista.
Ejercicio 3: Optimización de Uso de Memoria
Descripción del Problema
Dado un array de números enteros, queremos eliminar los duplicados y devolver un array con elementos únicos. El enfoque inicial utiliza una lista adicional para almacenar los elementos únicos.
Código Inicial
def remove_duplicates(arr):
unique_elements = []
for elem in arr:
if elem not in unique_elements:
unique_elements.append(elem)
return unique_elements
# Ejemplo de uso
arr = [1, 2, 2, 3, 4, 4, 5]
print(remove_duplicates(arr)) # Output: [1, 2, 3, 4, 5]Pasos para Optimizar
- Uso de Estructuras de Datos Adecuadas: Utilizar un conjunto (
set) para eliminar duplicados de manera eficiente. - Reducción de Uso de Memoria: Evitar el uso de una lista adicional.
Código Optimizado
def remove_duplicates_optimized(arr):
return list(set(arr))
# Ejemplo de uso
arr = [1, 2, 2, 3, 4, 4, 5]
print(remove_duplicates_optimized(arr)) # Output: [1, 2, 3, 4, 5]Explicación de la Optimización
- Uso de
set: Convertir el array a un conjunto elimina automáticamente los duplicados, y luego convertirlo de nuevo a una lista. - Reducción de Uso de Memoria: El uso de
setes más eficiente en términos de tiempo y espacio comparado con la lista adicional.
Conclusión
En esta sección, hemos abordado varios ejercicios prácticos para optimizar algoritmos en términos de tiempo y espacio. Hemos aprendido a:
- Mejorar la eficiencia de búsqueda utilizando estructuras de datos adecuadas.
- Optimizar algoritmos de ordenamiento mediante la detección de listas ordenadas y la reducción de comparaciones.
- Utilizar estructuras de datos eficientes para eliminar duplicados y reducir el uso de memoria.
Estos ejercicios no solo refuerzan los conceptos aprendidos, sino que también proporcionan técnicas prácticas que pueden aplicarse en situaciones del mundo real para mejorar el rendimiento del código.
Curso de Análisis y Diseño de Algoritmos
Módulo 1: Introducción a los Algoritmos
Módulo 2: Análisis de Algoritmos
- Análisis de Complejidad Temporal
- Análisis de Complejidad Espacial
- Casos de Complejidad: Mejor, Peor y Promedio
Módulo 3: Estrategias de Diseño de Algoritmos
Módulo 4: Algoritmos Clásicos
- Búsqueda Binaria
- Ordenamiento por Inserción
- Ordenamiento por Mezcla (Merge Sort)
- Ordenamiento Rápido (Quick Sort)
- Algoritmo de Dijkstra
- Algoritmo de Floyd-Warshall