6 - Análisis asintótico paso a paso

Una buena estimación de Big-O comienza identificando qué partes del código crecen con el tamaño de la entrada. En este tema seguimos un flujo práctico para algoritmos en Python y repasamos ejemplos clásicos.

6.1 Cómo analizar un algoritmo en Python

  • Define la entrada: qué significa n (tamaño de la lista, nodos, longitud de cadena).
  • Ubica operaciones dominantes: asignaciones, comparaciones, accesos a memoria repetidos.
  • Identifica ciclos y recursión: contar cuántas veces se ejecuta cada bloque.
  • Simplifica términos: conserva el factor de crecimiento que domina al aumentar n.
  • Comprueba con casos límite: n = 0, n = 1, y valores grandes para validar la intuición.

6.2 Contar operaciones dominantes

def suma(valores):
  total = 0                 # 1 operacion
  for valor in valores:     # se repite n veces
    total += valor          # 1 suma + 1 acceso por iteracion
  return total              # 1 operacion

La cantidad total de operaciones es proporcional a n; al descartar constantes queda O(n). El objetivo no es contar cada instrucción en ensamblador, sino encontrar la expresión que crece con n.

6.3 Loops anidados

for i in range(n):
  for j in range(n):
    # bloque O(1)
    pass

El bloque interno se ejecuta n veces por cada vuelta externa: n * n = n^2 operaciones dominantes. Si el límite interno depende de i (por ejemplo, j <= i), el conteo es n(n+1)/2, que sigue siendo O(n^2) por la simplificación asintótica.

6.4 Recorridos de listas

Recorrer una lista completa implica O(n), pero truncar el recorrido puede cambiar el escenario:

def contiene(valores, objetivo):
  for valor in valores:
    if valor == objetivo:
      return True  # mejor caso O(1)
  return False     # peor caso O(n)

Si la lista está ordenada y se usa búsqueda binaria, el mismo problema pasa a O(log n). Registrar cuándo el ciclo puede cortar antes ayuda a distinguir mejor, promedio y peor caso.

6.5 Recursión: ecuaciones de recurrencia

Un algoritmo recursivo se modela como una ecuación que relaciona T(n) con subproblemas más chicos:

  • T(n) = T(n-1) + O(1) → recorridos lineales (ej. imprimir lista enlazada). Solución: O(n).
  • T(n) = 2T(n/2) + O(n) → divide y vencerás con combinación lineal (ej. mergesort). Solución: O(n log n).
  • Aplicar el teorema maestro o expandir manualmente la recurrencia permite simplificar el orden.

6.6 Ejemplos prácticos

Suma de elementos (lineal):

def suma_elementos(valores):
  total = 0
  for valor in valores:
    total += valor
  return total  # O(n)

Bubble sort simplificado (cuadrático):

def bubble_sort(valores):
  n = len(valores)
  for i in range(n - 1):
    for j in range(n - i - 1):
      if valores[j] > valores[j + 1]:
        valores[j], valores[j + 1] = valores[j + 1], valores[j]
  # Dos loops anidados => O(n^2)

Si el array ya está ordenado podrías cortar temprano al detectar que no hubo intercambios, reduciendo el mejor caso a O(n).

Quicksort (visión previa):

def particion(valores, inicio, fin):
  pivote = valores[fin]
  i = inicio - 1
  for j in range(inicio, fin):
    if valores[j] <= pivote:
      i += 1
      valores[i], valores[j] = valores[j], valores[i]
  valores[i + 1], valores[fin] = valores[fin], valores[i + 1]
  return i + 1

def quicksort(valores, inicio, fin):
  if inicio >= fin:
    return
  p = particion(valores, inicio, fin)
  quicksort(valores, inicio, p - 1)
  quicksort(valores, p + 1, fin)

El tiempo esperado es O(n log n) si el pivote divide razonablemente. El peor caso (O(n^2)) ocurre si el pivote deja particiones muy desbalanceadas, algo que se mitiga eligiendo un pivote aleatorio o la mediana de tres.

Retornar