8 - Big-O y memoria en Python

La complejidad espacial describe cuánta memoria adicional usa un algoritmo respecto del tamaño de la entrada n. En Python la memoria se gestiona de forma automática, pero entender cómo crecen las estructuras es clave para evitar sobrecostos.

8.1 Asignaciones con listas

  • Complejidad espacial: crear una lista con k elementos ocupa O(k) referencias.
  • Costo temporal: las asignaciones son O(1) amortizado por la sobre-asignación.
  • Inicialización: construir listas con valores iniciales agrega costo lineal.
buffer = [0] * n

8.2 Crear y destruir nodos

Cada nodo en una lista, árbol o grafo aporta una unidad de memoria adicional. En Python, el recolector de basura libera cuando no hay referencias.

class Nodo:
  def __init__(self, valor, siguiente=None):
    self.valor = valor
    self.siguiente = siguiente

El uso de memoria es O(n) en cantidad de nodos. El costo temporal de recorrer la lista sigue siendo O(n).

8.3 Estructuras fijas vs dinámicas

  • Fijas: tuplas o arrays de tamaño conocido; espacio O(n) sin redimensionar.
  • Dinámicas: listas y diccionarios; permiten crecer pero pueden requerir copiar al duplicar capacidad (costo temporal).
  • Stack vs heap: Python gestiona el heap, pero la recursión consume stack y puede limitarse.
estatico = (0,) * 1024         # tupla fija
dinamico = [0] * n             # lista con tamaño depende de n

8.4 Estructuras grandes (matrices, grafos)

  • Matriz densa m x n: ocupa O(mn) celdas; en enteros de 4 bytes, 1000x1000 → ~4 MB.
  • Lista de adyacencia (grafo): nodos + aristas; espacio O(V + E).
  • Matriz de adyacencia: O(V^2); solo conviene en grafos densos.
def crear_matriz(filas, cols):
  return [[0] * cols for _ in range(filas)]

8.5 Fugas de memoria y su impacto

  • Definición: memoria reservada que ya no se referencia ni se libera.
  • Impacto: crece el uso de RAM; en procesos largos puede agotar memoria o degradar cache.
  • Prevención: evitar referencias circulares innecesarias, cerrar recursos y usar context managers.
with open("datos.txt", "r", encoding="utf-8") as archivo:
  contenido = archivo.read()
  procesar(contenido)

8.6 Herramientas de análisis de memoria

  • VSCode: permite inspeccionar uso de memoria con extensiones y el depurador.
  • tracemalloc: mapea asignaciones para encontrar crecimientos inesperados.
  • memory_profiler: mide consumo por línea en funciones críticas.
  • Buenas prácticas: aislar pruebas, medir con cargas reales y repetir varias veces.
Retornar