Big O Notation en Python: Ejemplos prácticos para cada complejidad

En nuestro artículo anterior sobre Big O Notation, exploramos las complejidades algorítmicas teóricas. Ahora, es el momento de llevar esa teoría a la práctica. Este artículo se centra en ejemplos prácticos en Python para cada una de las principales clases de complejidad, desde la eficiencia constante hasta la exponencial. Prepárate para sumergirte en la implementación real de algoritmos y comprender cómo la elección del enfoque afecta el rendimiento.

O(1) – Complejidad Constante

La complejidad constante es evidente en tareas que requieren tiempo constante, independientemente del tamaño de la entrada. Veamos un ejemplo simple en Python:

def constant_example(arr):
   return arr[0]

O(log n) – Complejidad Logarítmica

Los algoritmos logarítmicos son ideales para conjuntos de datos ordenados. Veamos la búsqueda binaria en Python:

def binary_search(arr, target):
   low, high = 0, len(arr) - 1
   while low <= high:
      mid = (low + high) // 2
      if arr[mid] == target:
         return mid
      elif arr[mid] < target:
         low = mid + 1
      else:
         high = mid - 1
   return -1

Este algoritmo divide repetidamente el conjunto de datos por la mitad hasta encontrar el elemento deseado.

O(n) – Complejidad Lineal

La complejidad lineal se observa en algoritmos donde el tiempo de ejecución es directamente proporcional al tamaño de la entrada. Aquí hay un ejemplo de búsqueda secuencial:

def linear_search(arr, target):
   for i, element in enumerate(arr):
      if element == target:
         return i
   return -1

Este algoritmo examina cada elemento del array secuencialmente hasta encontrar el objetivo.

O(n log n) – Complejidad Lineal Logarítmica

Ahora, veamos la eficiencia de un algoritmo de ordenación, como Quicksort, que tiene una complejidad O(nlog⁡n):

def quicksort(arr):
   if len(arr) <= 1:
      return arr
   pivot = arr[len(arr) // 2]
   left = [x for x in arr if x < pivot]
   middle = [x for x in arr if x == pivot]
   right = [x for x in arr if x > pivot]
   return quicksort(left) + middle + quicksort(right)

Este algoritmo divide y conquista, logrando eficiencia tanto lineal como logarítmica.

O(n^2) – Complejidad Cuadrática

La complejidad cuadrática se manifiesta en algoritmos con tiempo de ejecución proporcional al cuadrado del tamaño de la entrada. Un ejemplo es el algoritmo de ordenación burbuja:

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]

Este algoritmo realiza comparaciones y intercambios entre elementos en bucles anidados.

O(2^n) – Complejidad Exponencial

La complejidad exponencial se ilustra en problemas de fuerza bruta. Tomemos el ejemplo de generar todas las combinaciones posibles de una cadena:

def generate_combinations(s):
   if len(s) == 0:
      return ['']
   prev_combinations = generate_combinations(s[1:])
   new_combinations = []
   for combo in prev_combinations:
      new_combinations.append(combo)
      new_combinations.append(s[0] + combo)
   return new_combinations

Este algoritmo crea todas las combinaciones posibles, y su tiempo de ejecución crece exponencialmente con la longitud de la cadena.

En este recorrido de teoría a práctica con Big O Notation en Python, hemos llevado abstractos conceptos a la realidad del código. Desde la eficiencia constante hasta la complejidad exponencial, cada ejemplo ilustra cómo elegir el algoritmo adecuado es clave. Al recordar estos principios, no solo escribimos código funcional, sino eficiente, esencial cuando enfrentamos grandes conjuntos de datos.

También te puede interesar: