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 Python.

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

• Acceso aleatorio: O(1) por índice.
• Inserción al final: O(1) amortizado; O(n) si requiere crecer la capacidad.
• Inserción en medio: O(n) por corrimiento de elementos.
• Eliminación en medio: O(n) por corrimiento; al final es O(1).

def insertar(valores, pos, valor):
  valores.insert(pos, valor)  # corrimiento interno

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.

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

def push_front(head, valor):
  return Nodo(valor, head)

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).

def hash_simple(clave, mod):
  h = 5381
  for ch in clave:
    h = ((h << 5) + h) + ord(ch)
  return 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.

def sift_up(valores, idx):
  while idx > 0:
    padre = (idx - 1) // 2
    if valores[padre] <= valores[idx]:
      break
    valores[padre], valores[idx] = valores[idx], valores[padre]
    idx = padre