← Estructuras de datos desde cero · Lección 3/32

Cuánto cuesta: la O grande

1/8

Contar pasos, no segundos

Cuánto tarda un programa depende de la computadora, del teléfono, de qué más está abierto. Por eso se mide otra cosa: cuántos pasos da según el tamaño de la entrada, que se llama n.

Esta función suma un arreglo y cuenta sus vueltas. Con 3 elementos da 3 pasos; con 1000, 1000. El trabajo crece igual que n: se dice que es O(n), «de orden n» o lineal.

leccion.js

1function suma(arr) {
2  let total = 0, pasos = 0;
3  for (const x of arr) {
4    total += x;
5    pasos++;
6  }
7  console.log("n =", arr.length, "pasos =", pasos);
8  return total;
9}
10
11suma([4, 5, 6]);
12suma(new Array(1000).fill(1));

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

Pasos y n salen iguales: si el arreglo crece al doble, el trabajo crece al doble.

Toda la lección en una página

Contar pasos, no segundos

Cuánto tarda un programa depende de la computadora, del teléfono, de qué más está abierto. Por eso se mide otra cosa: cuántos pasos da según el tamaño de la entrada, que se llama n.

Esta función suma un arreglo y cuenta sus vueltas. Con 3 elementos da 3 pasos; con 1000, 1000. El trabajo crece igual que n: se dice que es O(n), «de orden n» o lineal.

1function suma(arr) {
2  let total = 0, pasos = 0;
3  for (const x of arr) {
4    total += x;
5    pasos++;
6  }
7  console.log("n =", arr.length, "pasos =", pasos);
8  return total;
9}
10
11suma([4, 5, 6]);
12suma(new Array(1000).fill(1));

Pasos y n salen iguales: si el arreglo crece al doble, el trabajo crece al doble.

Cuando cada uno se compara con todos

Si para cada elemento recorres otra vez el arreglo (dos ciclos, uno dentro del otro), los pasos crecen como n × n: O(n²), cuadrática. Con 10 elementos son 45 parejas; con 1000, casi medio millón.

En la O grande se ignoran las constantes y lo pequeño: n²/2 también es O(n²). Lo que importa es la forma en que crece cuando n se hace enorme.

1function parejas(n) {
2  let pasos = 0;
3  for (let i = 0; i < n; i++)
4    for (let j = i + 1; j < n; j++)
5      pasos++;
6  return pasos;
7}
8
9for (const n of [10, 100, 1000]) {
10  console.log(n, "->", parejas(n));
11}

Cada vez que n se multiplica por 10, los pasos se multiplican por unos 100. Así se ve una O(n²).

Partir a la mitad: O(log n)

Lo contrario de crecer rápido: si en cada paso descartas la mitad de lo que queda, un millón se acaba en 20 pasos. Eso es O(log n), logarítmica, y es la razón por la que buscar en algo ordenado es tan rápido.

Las familias, de la más barata a la más cara:

O(1) constante: leer arr[5].
O(log n): búsqueda binaria.
O(n): recorrer una vez.
O(n log n): ordenar bien.
O(n²): comparar todos contra todos.
O(2ⁿ): probar todas las combinaciones.

1function mitades(n) {
2  let pasos = 0;
3  while (n > 1) {
4    n = Math.floor(n / 2);
5    pasos++;
6  }
7  return pasos;
8}
9
10for (const n of [8, 1024, 1_000_000]) {
11  console.log(n, "->", mitades(n));
12}

Un millón en 19 pasos. Multiplicar n por mil apenas suma unos 10 pasos.