Contar operaciones permite estimar el costo de un algoritmo a partir de su estructura. Es el primer paso para comparar soluciones sin depender de la velocidad de una computadora particular.
Un algoritmo ejecuta instrucciones: asignaciones, comparaciones, sumas, accesos a estructuras y llamadas. El conteo de operaciones construye una función T(n) que expresa cuántas acciones relevantes se realizan para una entrada de tamaño n.
No buscamos contar exactamente cada ciclo de procesador. Elegimos un modelo simple y coherente que permite descubrir cómo cambia el trabajo cuando la entrada crece. Luego usaremos notación asintótica para ignorar detalles que no dominan el crecimiento.
En un modelo básico, tratamos como operaciones de costo constante las acciones que no dependen del tamaño de la entrada: asignar una variable, comparar dos números, sumar dos números acotados, acceder a un elemento por índice o devolver un resultado.
| Instrucción | Costo simplificado | Observación |
|---|---|---|
x = 0 | Constante | Una asignación. |
a < b | Constante | Una comparación. |
suma += valor | Constante | Suma y asignación. |
arreglo[i] | Constante en un arreglo | Acceso directo por índice. |
ordenar(arreglo) | No necesariamente constante | Depende del algoritmo usado. |
El modelo debe respetar la estructura del problema. Por ejemplo, comparar enteros de tamaño fijo se considera constante, pero comparar cadenas muy largas puede depender de su longitud.
Antes de contar debemos definir n. En un arreglo, n suele ser la cantidad de elementos. En una matriz puede haber filas y columnas; en un grafo, vértices y aristas; en un entero, la cantidad de bits necesarios para representarlo.
Cuando las instrucciones se ejecutan una después de otra, sus costos se suman. Si una parte realiza c1 operaciones y la siguiente c2, el total es c1 + c2.
Agregar una cantidad fija de instrucciones no cambia la clase de complejidad. Un algoritmo que ejecuta 5 o 500 operaciones constantes sigue siendo Θ(1) respecto de n.
Un bucle que se repite n veces y ejecuta una operación constante en cada iteración tiene costo lineal. También debemos considerar inicialización, comparación de salida e incremento, aunque todos son proporcionales a n.
function sumarYContar(n) {
let suma = 0;
let sumas = 0;
for (let i = 1; i <= n; i++) {
suma += i;
sumas++;
}
return { suma, sumas };
}
console.log(sumarYContar(10)); // { suma: 55, sumas: 10 }La función cuenta las operaciones principales de suma. Para n = 10 realiza diez sumas; para n = 1 000 000 realiza un millón. La relación principal es lineal.
Si un bucle de n iteraciones contiene otro bucle de n iteraciones, el cuerpo interno se ejecuta n · n = n² veces. Los bucles anidados multiplican sus repeticiones cuando sus rangos son independientes.
function contarParesOrdenados(n) {
let operaciones = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
operaciones++;
}
}
return operaciones;
}
console.log(contarParesOrdenados(5)); // 25El algoritmo realiza una operación por cada par ordenado (i, j). Para n = 5 hay 5² = 25 pares; para n = 100 hay 10 000.
Los bucles anidados no siempre realizan n² iteraciones. Si el límite interno depende del índice externo, debemos sumar la cantidad de repeticiones de cada fila.
La constante 1/2 no cambia la clase asintótica, pero el conteo exacto revela que este algoritmo realiza aproximadamente la mitad de las iteraciones de uno con dos bucles independientes.
function contarParesSinRepeticion(n) {
let pares = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
pares++;
}
}
return pares;
}
console.log(contarParesSinRepeticion(5)); // 10La cantidad es (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2. El algoritmo cuenta cada par no ordenado una sola vez y sigue teniendo crecimiento cuadrático.
Un bucle no siempre incrementa de a uno. Si una variable se duplica en cada iteración, el número de repeticiones es logarítmico. Después de k duplicaciones, su valor es 2k.
function contarDuplicaciones(limite) {
let valor = 1;
let pasos = 0;
while (valor < limite) {
valor *= 2;
pasos++;
}
return { valorFinal: valor, pasos };
}
console.log(contarDuplicaciones(100)); // { valorFinal: 128, pasos: 7 }Solo se necesitan siete duplicaciones para superar 100. Para superar aproximadamente un millón se necesitan cerca de veinte, lo que ilustra la lentitud del crecimiento logarítmico.
En un condicional se cuenta el costo de evaluar la condición más el costo de la rama que se ejecuta. Si el algoritmo puede seguir rutas diferentes, debemos especificar si analizamos el mejor caso, el peor caso o el costo promedio.
| Medida | Descripción | Ejemplo de búsqueda lineal |
|---|---|---|
| Mejor caso | Menor costo entre entradas de tamaño n. | El valor está en la primera posición. |
| Peor caso | Mayor costo entre entradas de tamaño n. | No está o aparece al final. |
| Caso promedio | Costo esperado bajo una distribución definida. | Depende de cómo se distribuyan los valores buscados. |
function buscarYContar(numeros, buscado) {
let comparaciones = 0;
for (let i = 0; i < numeros.length; i++) {
comparaciones++;
if (numeros[i] === buscado) {
return { indice: i, comparaciones };
}
}
return { indice: -1, comparaciones };
}
console.log(buscarYContar([4, 8, 15, 16, 23], 4)); // { indice: 0, comparaciones: 1 }
console.log(buscarYContar([4, 8, 15, 16, 23], 42)); // { indice: -1, comparaciones: 5 }La búsqueda puede terminar en una comparación o necesitar n comparaciones. Su complejidad de peor caso es Θ(n), aunque su mejor caso sea Θ(1).
En un algoritmo real hay muchas instrucciones, pero algunas se repiten con mayor frecuencia y dominan el costo. Contar una operación representativa simplifica el análisis sin perder la tendencia principal.
Si una operación aparentemente constante oculta una tarea costosa, como copiar un arreglo entero, debemos contar esa tarea de forma explícita.
El conteo exacto puede producir expresiones como 3n² + 7n + 12. Para entradas grandes, el término de mayor grado domina. Por eso 3n² + 7n + 12 tiene crecimiento cuadrático.
La notación Big-O, Omega y Theta formalizará esta comparación en los próximos temas.
No todos los algoritmos dependen de un único tamaño n. Si recorremos una matriz de r filas y c columnas, el cuerpo se ejecuta r · c veces. Si recorremos un grafo, el costo puede depender de V y E.
Forzar todos los tamaños a una sola variable puede ocultar la estructura importante del problema. Conviene mantener los parámetros independientes mientras sea relevante.
Contar operaciones permite transformar código en una expresión matemática y descubrir cómo escala un algoritmo. En el próximo tema estudiaremos el crecimiento de funciones para comparar esos costos con mayor precisión.