8 - Big-O y memoria en C

La complejidad espacial describe cuánta memoria adicional usa un algoritmo respecto del tamaño de la entrada n. En C el control de memoria es manual, por lo que entender cómo crecen las estructuras es clave para evitar fugas y sobrecostos.

8.1 Asignaciones con malloc

  • Complejidad espacial: reservar k elementos de sizeof(T) ocupa O(k) bytes.
  • Costo temporal: malloc suele ser O(1) amortizado, aunque depende del asignador.
  • Inicialización: usar calloc agrega costo lineal por poner ceros.
int *buffer = malloc(sizeof(int) * n);
if (!buffer) {
  perror("malloc");
  return 1;
}

8.2 Crear y destruir nodos

Cada nodo en una lista, árbol o grafo aporta una unidad de memoria adicional. Liberar de forma simétrica es esencial.

typedef struct Nodo {
  int valor;
  struct Nodo *sig;
} Nodo;

Nodo *crear_nodo(int valor) {
  Nodo *n = malloc(sizeof(Nodo));
  if (!n) return NULL;
  n->valor = valor;
  n->sig = NULL;
  return n;
}

void destruir_lista(Nodo *head) {
  while (head) {
    Nodo *tmp = head->sig;
    free(head);
    head = tmp;
  }
}

El uso de memoria es O(n) en cantidad de nodos. El recorrido de destrucción también es O(n) en tiempo.

8.3 Arreglos estáticos vs dinámicos

  • Estáticos: tamaño fijo en tiempo de compilación o en el stack; espacio O(n) pero sin redimensionar.
  • Dinámicos: se reservan en heap; permiten crecer pero pueden requerir copiar al duplicar capacidad (costo temporal).
  • Stack vs heap: el stack suele ser más limitado; arrays grandes deben ir al heap.
int estatico[1024];          // en stack, tamaño fijo
int *dinamico = malloc(n * sizeof(int)); // en heap, 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.
// Matriz dinamica simple fila contigua
int **crear_matriz(int filas, int cols) {
  int *datos = malloc(sizeof(int) * filas * cols);
  int **m = malloc(sizeof(int*) * filas);
  for (int i = 0; i < filas; i++) {
    m[i] = datos + i * cols;
  }
  return m;
}

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: patrones de propiedad claros, funciones destroy simétricas, revisar errores tempranos.
char *linea = malloc(256);
if (!linea) return -1;
if (leer(linea) != 0) {
  free(linea);  // evitar fuga en rutas de error
  return -1;
}
procesar(linea);
free(linea);

8.6 CLion y herramientas de análisis de memoria

  • CLion: integra sanitizers (AddressSanitizer, LeakSanitizer) y detecta fugas y accesos ilegales.
  • Valgrind: valgrind --leak-check=full ./programa reporta fugas y usos incorrectos; agrega sobrecosto pero es exhaustivo.
  • Heap profiler: usar herramientas de muestreo ayuda a ver qué estructuras crecen y si cumplen el Big-O esperado.
  • Buenas prácticas: activar depuración (-g) y compilar sin optimizaciones agresivas al analizar.
Retornar