7 - Análisis de complejidad en estructuras de datos

Las estructuras de datos determinan la eficiencia de las operaciones básicas. A continuación resumimos complejidad temporal (y cuando aplica, espacial) en escenarios típicos al trabajar con C.

7.1 Arrays (acceso, inserción, eliminación)

• Acceso aleatorio: O(1) por aritmética de punteros.
• Inserción al final: O(1) si hay capacidad disponible; O(n) si requiere copiar a un buffer más grande.
• Inserción en medio: O(n) por corrimiento de elementos.
• Eliminación en medio: O(n) por corrimiento; al final es O(1).

void insertar(int *v, int *n, int pos, int valor) {
  for (int i = *n; i > pos; i--) v[i] = v[i - 1]; // corrimiento
  v[pos] = valor;
  (*n)++;
}

7.2 Listas enlazadas

• Acceso por índice: O(n); hay que recorrer nodo a nodo.
• Inserción/eliminación al inicio: O(1) usando la cabeza.
• Inserción/eliminación tras un nodo conocido: O(1); localizar el nodo es lo costoso.
• Memoria: cada nodo guarda puntero; uso total O(n) pero con sobrecosto por punteros.

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

void push_front(Nodo **head, int valor) {
  Nodo *nuevo = malloc(sizeof(Nodo));
  nuevo->dato = valor;
  nuevo->sig = *head;
  *head = nuevo;
}

7.3 Pilas y colas

Pila (stack LIFO):

• Implementada con array o lista: push/pop son O(1).
• Crecimiento del array puede costar O(n) puntual, pero amortizado O(1) si se duplica capacidad.

Cola (FIFO):

• Con arreglo circular: enqueue/dequeue en O(1).
• Con lista enlazada: operaciones también O(1) si se mantiene puntero a cabeza y cola.

7.4 Árboles binarios

• Altura h: determina la complejidad; para un árbol balanceado h = O(log n), degenerado h = O(n).
• Recorrido completo: O(n) ya que visita cada nodo una vez.
• Inserción/búsqueda: O(h), depende de la altura real.

7.5 BST equilibrado vs degenerado

• Balanceado: AVL o Red-Black mantienen O(log n) para insertar, buscar y eliminar.
• Degenerado: si los valores llegan ordenados y no hay rotaciones, el BST se vuelve lista y pasa a O(n).
• El costo de rotar/rebalancear es O(1) por operación, por eso el orden amortizado se conserva.

7.6 Hashing: O(1*) amortizado

• Inserción/búsqueda promedio: O(1) si la función hash distribuye bien y la tabla se redimensiona.
• Peor caso: O(n) si todas las claves colisionan; se mitiga con buena función hash y resize.
• Rehash: crecer la tabla a veces cuesta O(n), pero ocurre cada varios inserts → amortizado O(1).

typedef struct Entrada {
  const char *clave;
  int valor;
} Entrada;

int hash(const char *s, int mod) {
  unsigned h = 5381;
  for (; *s; s++) h = ((h << 5) + h) + (unsigned char)(*s);
  return (int)(h % mod);
}

7.7 Heaps: O(log n)

• Insertar (push): O(log n) por subir el elemento.
• Extraer mín/máx: O(log n) por bajar el elemento.
• Consultar tope: O(1) porque está en la raíz.
• Construir heap desde array: O(n) usando heapify de abajo hacia arriba.

void sift_up(int *v, int idx) {
  while (idx > 0) {
    int padre = (idx - 1) / 2;
    if (v[padre] <= v[idx]) break;
    int tmp = v[padre];
    v[padre] = v[idx];
    v[idx] = tmp;
    idx = padre;
  }
}