Complejidad asintótica (Big-O)

Diagrama de estructuras de datos: arbol binario, lista enlazada y tabla hash. — Estructuras de datos fundamentales y analisis de complejidad algoritmica.

Mapa conceptual

Estructuras de Datos
- Lineales
  - Arrays
  - Listas enlazadas
  - Pilas y Colas
- No lineales
  - Arboles BST
  - Heaps
  - Grafos
- Hash
  - Funcion hash
  - Colisiones
  - Rehashing
- Algoritmos
  - Ordenamiento
  - Busqueda binaria
  - BFS DFS
- Optimizacion
  - Big-O
  - Dinamica
  - Voracidad

Big-O describe el término que domina cuando n crece, ignorando constantes y términos menores. Dos bucles anidados sobre n dan O(n²); un bucle simple y uno anidado siguen siendo O(n²). Un bucle más un anidado independientes (n + n²) es O(n²), porque n se desprecia frente a n².

La jerarquía de crecimiento

Crecimiento relativo (n en potencias de 2)

La escala real importa: n = 10⁶ hace que O(n) sea factible (~un millón de pasos), O(n log n) cómodo, O(n²) inviable (10¹² pasos) y O(2ⁿ) inimaginable.

Nota el salto: pasar de O(n²) a O(n log n) sobre 1 000 elementos multiplica por 100 la velocidad; sobre un millón, por 10 000.
Complejidad	Algoritmo típico	n = 1 000
O(1)	acceso a índice, hash	1 operación
O(log n)	búsqueda binaria	≈ 10 operaciones
O(n)	recorrido lineal	1 000 operaciones
O(n log n)	mergesort, quicksort medio	≈ 10 000
O(n²)	burbuja, dos bucles anidados	1 000 000
O(2ⁿ)	fuerza bruta de subconjuntos	absurdo

No es solo tiempo: espacio

La complejidad espacial mide memoria extra. Un algoritmo in-place (ordena sin copiar la lista) es O(1) de espacio; uno que construye una copia es O(n). A veces se cambia espacio por tiempo: una tabla hash usa memoria extra para comprar búsquedas constantes.

¿Cuál es la complejidad temporal del siguiente código? for i in range(n): for j in range(n): x += 1

Un algoritmo O(n) es siempre más rápido en la práctica que uno O(n log n).

Ordena las clases de complejidad de más rápida (menos trabajo) a más lenta.

Arrastra cada ficha a su categoría (o tócala y luego toca la categoría). También puedes usar el teclado.

Une cada situación con la decisión de ingeniería que la complejidad sugiere.

Errores al estimar

Contar operaciones internas y olvidar que n es el tamaño de la ENTRADA, no del resultado.
Quedarse con el peor caso cuando el caso medio es representativo (quicksort: O(n²) pesimista pero O(n log n) medio).
Ignorar la complejidad escondida de una operación: buscar en una lista es O(n), y meter eso dentro de un bucle convierte un O(n) en O(n²) sin que lo veas.

Ejemplo resuelto

Analiza: for i in range(n): if i in lista_grande: ...
El bucle exterior es O(n).
Pero i in lista sobre una lista es O(m) con m el tamaño de la lista.
Total: O(n·m), no O(n).
Arreglo: convertir lista_grande a un conjunto (set) hace la pertenencia O(1) y el todo O(n).

En ciencia de datos, el 90 % de la lentitud de un pipeline no está en el modelo sino en estructuras mal elegidas: un in sobre una lista dentro de un bucle, un DataFrame filtrado fila a fila, o ordenar varias veces. Leer Big-O te dice dónde duele antes de escribir una línea.

Tabla de bolsillo

O(1)

constante

O(log n)

dobla o parte a la mitad

O(n)

lineal: recorre una vez

O(n log n)

ordenar eficiente

O(n²)

dos bucles anidados

O(2ⁿ)

subconjuntos, fuerza bruta

amortizado

promedio tras muchas operaciones

in-place

O(1) de espacio

Toca una tarjeta para ver la respuesta.

Análisis de algoritmos (repaso formal)Notación asintótica, mejores y peores casos con ejemplos.

Video complementario

Recurso audiovisual para reforzar los conceptos.

Tienes que responder «¿esta transacción es fraudulenta?» para 10⁷ transacciones. Un enfoque compara cada transacción con las 10⁴ anteriores (O(n·m)) y otro mantiene un conjunto de patrones vistos (O(n)). Calcula órdenes de magnitud de ambos y argumenta cuál usarías.

Tu texto se guarda sólo en este dispositivo.

VisuAlgoVisualizaciones animadas de estructuras de datos y algoritmos.

Complejidad asintótica (Big-O)

Herramientas de la lección

Sobre este contenido

Ir a