Calculadora de complejidad temporal Big O

Comparar modelos de crecimiento para un tamaño de entrada

La calculadora evalúa ocho funciones de crecimiento para un tamaño n y divide cada cuenta entre una tasa de operaciones por segundo. Permite comparar cómo aumenta el trabajo de los modelos y explorar un presupuesto de tiempo aproximado. Selecciona una función que corresponda al análisis del algoritmo antes de interpretar su duración.

El ejemplo inicial utiliza n = 1000, mil millones de operaciones por segundo y el modelo n log₂ n. Se obtienen aproximadamente 9965,784285 operaciones, equivalentes a 9,966 microsegundos. Al seleccionar n² con el mismo tamaño y tasa, aparecen un millón de operaciones y un milisegundo.

Estos tiempos pertenecen al modelo introducido. El formulario no inspecciona código, mide un procesador ni deduce automáticamente la complejidad de una función. Tampoco determina cuántas instrucciones de máquina corresponden a una operación conceptual. Define primero qué representa esa operación para que la comparación tenga un significado coherente.

Separar una cota asintótica de una cuenta exacta

La definición de notación O grande del NIST expresa una cota superior asintótica mediante una constante multiplicativa fija para entradas suficientemente grandes. No es una igualdad que proporcione el número exacto de operaciones para todos los tamaños de entrada.

Por ejemplo, n² y 3n² + 100n tienen una cota O(n²). Esta página evalúa la función representativa n², sin añadir el coeficiente tres ni el término de menor orden. Para n = 1000, la segunda expresión da 3,1 millones, mientras que el modelo n² mostrado da un millón.

Dos implementaciones pueden pertenecer a la misma clase de complejidad y realizar distinto trabajo por iteración. También pueden asignar diferente memoria o responder de otra manera a la distribución de los datos. Una mejor cota asintótica no implica necesariamente menor tiempo para todas las entradas pequeñas. La medición real y el análisis de crecimiento aportan información complementaria.

Distingue asimismo entre peor caso, caso medio y mejor caso. Elegir una curva no determina a cuál de esos análisis corresponde. Si un algoritmo tiene cotas diferentes según sus entradas, compáralas como escenarios separados y registra qué representa cada una. El selector cambia la función matemática, no la interpretación del caso.

Elegir n y una tasa de trabajo útil

El tamaño debe ser un entero de 1 a 1000000000. Decide qué cuenta n: elementos de una lista, vértices, candidatos u otra cantidad. Una expresión con vértices y aristas no puede reducirse en general a un único n sin una hipótesis adicional que relacione ambas variables.

La tasa debe ser positiva. El valor inicial de 10^9 operaciones por segundo es una hipótesis editable para comparar funciones. No afirma que una máquina pueda completar esa cantidad de consultas de base de datos, asignaciones, comparaciones de cadenas o peticiones de red cada segundo.

Mantén una unidad de trabajo consistente. Si mediste un millón de operaciones relevantes en dos segundos, una tasa inicial sería 500000 operaciones por segundo. Esa tasa puede cambiar para entradas mayores si limitan la memoria, la contención o la entrada/salida. Introducir una tasa medida no elimina esas dependencias.

Cambiar solo la tasa modifica inversamente todos los tiempos. Multiplicarla por diez divide cada duración entre diez y conserva las cuentas de operaciones. Así puedes comparar por separado una hipótesis de rendimiento y un cambio en el modelo de crecimiento, sin atribuir al algoritmo una mejora que procede únicamente de la tasa supuesta.

Interpretar las ocho funciones

El modelo constante vale uno. El logarítmico utiliza log₂ n y el lineal, n. El modelo combinado es n log₂ n. Después aparecen n², n³, la función exponencial 2^n y el factorial n!. Las funciones describen tendencias diferentes incluso cuando coinciden para algunos valores pequeños.

El resultado logarítmico no tiene por qué ser entero. Para n = 1000, log₂ n es aproximadamente 9,965784. Es el valor de la función continua, no una afirmación de que una búsqueda binaria real haga una fracción de comparación. Una cuenta exacta requiere reglas de redondeo y terminación del algoritmo concreto.

Para n = 1, log₂ n y n log₂ n son cero. Por eso esas selecciones muestran cero operaciones y tiempo de modelo. Un programa real conserva costes de preparación y retorno que estas funciones simplificadas no incluyen. Los factoriales se calculan directamente hasta n = 2000; por encima se utiliza una aproximación mediante log-gamma.

Leer el gráfico junto con la tabla

El eje vertical representa log₁₀ de la cuenta de operaciones. Pasar de seis a nueve significa multiplicar de un millón a mil millones, un factor de mil. La referencia horizontal de un segundo corresponde a la tasa seleccionada. Las curvas se recortan en el límite superior del gráfico y los ceros se omiten porque su logaritmo no está definido.

La tabla evalúa las ocho funciones para el n elegido aunque una curva ya quede fuera de la zona visible. Las cuentas se redondean a seis cifras significativas y los logaritmos a tres posiciones decimales. El CSV contiene esos valores de tabla, incluido el redondeo ya aplicado, no una expansión exacta completa de cantidades enormes.

Todas las filas utilizan 10^9 operaciones por segundo. Los modelos exponencial y factorial emplean n = 100 y n = 20; el último, n = 1. Los dos primeros usan n = 1000. Compara estas hipótesis y después mide el programa. La calculadora de ancho de banda modela otra restricción si domina la transferencia. El conversor de bases cambia la escritura de números, sin cambiar el crecimiento del algoritmo.