Skip to main content

Abrir el simulador

Cuenta operaciones en el mejor, el peor y el caso medio para cada talla, con gráfica y tabla.
¿Cuánto tarda un algoritmo? Depende del ordenador, del lenguaje y, sobre todo, de los datos: del tamaño de la entrada y, a veces, de cómo estén colocados. Para comparar algoritmos de forma justa se cuenta cuántas veces se ejecuta la operación crítica y se estudia cómo crece con la talla, en el mejor, el peor y el caso medio.

​
Lo que vas a aprender

  • Qué son la talla de la entrada y la operación crítica.
  • Distinguir mejor caso, peor caso y caso medio.
  • Expresar el coste con la notación O.
  • Comprobar experimentalmente el orden de un algoritmo.

​
Cómo se usa el simulador

  • Elige el algoritmo: búsqueda lineal, matriz por vector, inserción o búsqueda binaria.
  • Elige la talla máxima (100 – 1000).
  • La gráfica dibuja las operaciones según la talla en el mejor, medio y peor caso.
  • La tabla da los resultados para cada talla y una columna que divide el peor caso entre la función teórica: si se estabiliza en una constante, se confirma el orden.
  • Se muestra el código en C con la operación que se cuenta, qué entrada da cada caso y cómo se mide el tiempo con clock().

​
Fundamentos teóricos

​
Talla y operación crítica

  • Talla (nn): el tamaño de la entrada (elementos de un vector, filas de una matriz…).
  • Operación crítica: la que más veces se ejecuta. Contarla es proporcional al tiempo y no depende del ordenador.

​
Los tres casos

  • Mejor caso: la entrada de talla nn que menos trabajo da.
  • Peor caso: la que más trabajo da. Es una garantía: nunca tardará más.
  • Caso medio: lo que cuesta de media con entradas al azar.
Si el trabajo solo depende de nn (sumar un vector, multiplicar matrices), los tres casos coinciden.

​
Notación O

f(n)=O(g(n))f(n) = O(g(n)) significa que, para nn grande, ff crece como mucho como gg (salvo constantes). Órdenes típicos, de menor a mayor: O(1)<O(log⁡n)<O(n)<O(nlog⁡n)<O(n2)<O(n3)<O(2n)O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n)

​
Algoritmos del simulador

​
Análisis experimental

  1. Elegir varias tallas.
  2. Para cada una, generar entradas del caso que se estudia y contar operaciones (o medir tiempo).
  3. Dibujar la gráfica talla–operaciones.
  4. Dividir entre la función teórica: si el cociente tiende a una constante, se confirma.
Al medir tiempos reales con clock(), se repite la ejecución muchas veces y se divide, porque con tallas pequeñas una sola ejecución dura menos que la resolución del reloj.

​
Ejemplos resueltos

Ejemplo 1 · Búsqueda lineal

En un vector de 1000 elementos: mejor caso 1 comparación (está en V[0]); peor caso unas 1000 (no está); caso medio unas 500.
Con 100 elementos ya ordenados: 99 comparaciones. Al revés: 100⋅99/2=4950100 \cdot 99/2 = 4950.
Con 1000 elementos, el peor caso es de unas 10 comparaciones; con un millón, unas 20.

​
Experimenta con el simulador

1

Lineal

Mira la columna “peor / n” de la búsqueda lineal. ¿Se estabiliza?
2

Inserción

Compara las tres curvas de la inserción. ¿Por qué el mejor caso es una recta?
3

Logarítmico

Con la búsqueda binaria, duplica la talla máxima. ¿Cuánto crece el peor caso?

​
Errores frecuentes

  • Decir que el mejor caso es n=1n = 1. Los casos se comparan a igual talla.
  • Confundir caso medio con la media entre mejor y peor.
  • Quedarse con las constantes al dar el orden: 3n+53n + 5 es O(n)O(n).

​
Herramientas relacionadas

Algoritmos de ordenación

Mejor y peor caso de cada algoritmo.

Divide y vencerás

Ecuaciones de recurrencia.

Regresión lineal

Ajustar datos experimentales.
Última modificación el 6 de octubre de 2026