Notación Big-O y complejidad de algoritmos en C#

Problema

¿Aguantará con un millón?

La tienda firmó un contrato con un gran proveedor. En un mes el catálogo pasa de 1000 a 1 000 000 de productos. En el código hay seis funciones por las que pasa cada producto o cada pago:

el primer precio de la lista (para el banner de la página de inicio);
la búsqueda de un precio en la lista ordenada de precios;
la suma de los precios (para el informe);
la ordenación de los precios (para la página «Primero los más baratos»);
la comprobación de pagos dobles de la lección anterior;
todas las combinaciones de productos que caben en el presupuesto del cliente.

¿Cuáles aguantarán? Todavía no hay datos con un millón de productos, y los segundos de tu laptop mienten de todos modos. Tienes que saberlo por el código. Contar cada paso exactamente, como con n(n − 1) / 2, es lento. Y los detalles no importan: lo que importa es cómo crece el trabajo.

La idea

Big-O: qué hace duplicar

Big-O es un nombre corto para cómo crece el número de operaciones cuando crece n (la cantidad de datos). No dice segundos, dice una forma: qué le pasa al trabajo cuando los datos se duplican.

Clase	Nombre	Ejemplo de la tienda	n se duplica → el trabajo
O(1)	constante	el primer precio	no cambia
O(log n)	logarítmica	búsqueda en la lista ordenada de precios	un paso más
O(n)	lineal	la suma de los precios	×2
O(n log n)	«n log n»	ordenación	un poco más de ×2
O(n²)	cuadrática	pagos dobles	×4
O(2ⁿ)	exponencial	todas las combinaciones dentro del presupuesto	al cuadrado

Aquí están las seis funciones. Los precios están en centavos de euro, así que son números enteros:

static int FirstPrice(int[] prices)
{
    return prices[0];
}

static int Total(int[] prices)
{
    int sum = 0;
    foreach (int p in prices)
    {
        sum += p;
    }
    return sum;
}

static int DoublePayments(int[] ids)
{
    int found = 0;
    for (int i = 0; i < ids.Length; i++)
    {
        for (int j = i + 1; j < ids.Length; j++)
        {
            if (ids[i] == ids[j])
            {
                found++;
            }
        }
    }
    return found;
}

FirstPrice hace un paso, sin importar cuántos precios haya. Total hace uno por precio. DoublePayments hace uno por cada par.

Míralo

O(log n): cuántas veces divides a la mitad

La búsqueda en la lista ordenada de precios mira el medio. Si el precio que buscas es mayor, la mitad izquierda no hace falta para nada y se descarta. Si no, se va la mitad derecha. Así, después de cada comprobación queda la mitad:

static int IndexOf(int[] sorted, int price)
{
    int lo = 0;
    int hi = sorted.Length - 1;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (sorted[mid] == price)
        {
            return mid;
        }
        else if (sorted[mid] < price)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return -1;
}

¿Cuántas comprobaciones si el precio no está? Tantas como veces puedas dividir n a la mitad antes de que no quede nada. Eso es el logaritmo: log₂ n es «cuántas veces divides a la mitad».

foreach (int n in new[] { 1000, 100000, 1000000, 1000000000 })
{
    int halvings = 0;
    for (int left = n; left > 0; left /= 2)
    {
        halvings++;
    }
    Console.WriteLine(n + " → " + halvings);
}

1000 → 10
100000 → 17
1000000 → 20
1000000000 → 30

Mil veces más precios (de 1000 a 1 000 000) son solo 10 comprobaciones más. Duplicar añade una. Por eso O(log n) casi no crece.

Más sobre los límites de la búsqueda binaria (y dónde uno se equivoca por uno) viene en la lección «Búsqueda binaria».

Míralo

O(n log n) y O(2ⁿ)

La ordenación usa la función integrada Array.Sort:

static int[] SortedPrices(int[] prices)
{
    int[] copy = (int[])prices.Clone();
    Array.Sort(copy);
    return copy;
}

Los buenos algoritmos de ordenación dividen el array en mitades (log n niveles) y en cada nivel recorren todo una vez (n pasos). Por eso son O(n log n). Cómo exactamente lo verás en la lección sobre merge sort.

Las combinaciones dentro del presupuesto: para cada producto hay dos opciones, «tomarlo» o «dejarlo». Por eso Combos se llama a sí misma dos veces:

static int Combos(int[] prices, int i, int sum, int budget)
{
    if (i == prices.Length)
    {
        return sum <= budget ? 1 : 0;
    }
    return Combos(prices, i + 1, sum, budget)
        + Combos(prices, i + 1, sum + prices[i], budget);
}

Con 1 producto hay 2 combinaciones, con 2 hay 4, con 3 hay 8. Cada producto nuevo duplica todo lo que había hasta ahora. Eso es O(2ⁿ).

Las seis, ejecutadas con cinco precios y cinco pagos:

int[] prices = { 1299, 450, 3999, 899, 2450 };
int[] sorted = SortedPrices(prices);
int[] payments = { 100231, 100232, 100233, 100232, 100234 };
Console.WriteLine("Primer precio: " + FirstPrice(prices));
Console.WriteLine("2450 está en el índice " + IndexOf(sorted, 2450));
Console.WriteLine("Suma: " + Total(prices));
Console.WriteLine("Más barato: " + sorted[0] + ", más caro: " + sorted[4]);
Console.WriteLine("Pagos dobles: " + DoublePayments(payments));
Console.WriteLine("Combinaciones hasta 5000: " + Combos(prices, 0, 0, 5000));

Primer precio: 1299
2450 está en el índice 3
Suma: 9097
Más barato: 450, más caro: 3999
Pagos dobles: 1
Combinaciones hasta 5000: 18

Míralo

Qué hace duplicar

static int Combos(int[] prices, int i, int sum, int budget)
{
    if (i == prices.Length)
    {
        return sum <= budget ? 1 : 0;
    }
    return Combos(prices, i + 1, sum, budget)
        + Combos(prices, i + 1, sum + prices[i], budget);
}

static int IndexOf(int[] sorted, int price)
{
    int lo = 0;
    int hi = sorted.Length - 1;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (sorted[mid] == price)
        {
            return mid;
        }
        else if (sorted[mid] < price)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return -1;
}

static int DoublePayments(int[] ids)
{
    int found = 0;
    for (int i = 0; i < ids.Length; i++)
    {
        for (int j = i + 1; j < ids.Length; j++)
        {
            if (ids[i] == ids[j])
            {
                found++;
            }
        }
    }
    return found;
}

static int Combos(int[] prices, int i, int sum, int budget)
{
    if (i == prices.Length)
    {
        return sum <= budget ? 1 : 0;
    }
    return Combos(prices, i + 1, sum, budget)
        + Combos(prices, i + 1, sum + prices[i], budget);
}

Paso a paso, en palabras

El primer precio: un paso con 4 precios y con 8. El trabajo no depende de n: O(1).
La búsqueda binaria mira el medio y descarta la mitad. 4 → 2 → 1 son 3 comprobaciones, 8 → 4 → 2 → 1 son 4. El doble de precios, una comprobación más: O(log n).
La suma recorre cada precio una vez: 4 y 8 pasos. El doble de precios, el doble de trabajo: O(n).
La ordenación mezcla nivel por nivel (aquí merge sort, como en Bench). Hay log n niveles, con como máximo n comparaciones en cada uno: 5 → 16. O(n log n).
Pagos dobles: cada uno con cada uno de los que vienen después. 6 → 28: el triángulo crece en dos direcciones. O(n²).
Combinaciones dentro del presupuesto: cada producto se «toma» o se «deja», y cada uno nuevo duplica la cantidad. 16 → 256: con 8 productos el trabajo es el de 4, al cuadrado. O(2ⁿ).

Las seis clases con 4 y con 8 precios. Cada cubo es un paso, exactamente tantos como cuenta Bench. O(1) no se mueve. O(log n) añade una barra. O(n) se duplica. O(n log n) se duplica y gana un nivel más. O(n²) crece en dos direcciones. O(2ⁿ) pasa de un cuadrado de 4 × 4 a uno de 16 × 16.

La idea

Las constantes y los términos pequeños desaparecen

El informe de pagos dobles hace n(n − 1) / 2 = n²/2 − n/2 pasos. ¿Por qué es O(n²) y no O(n²/2 − n/2)?

El término menor desaparece al crecer n:

n	n²/2	n/2	n/2 como parte del total
10	50	5	10 %
1000	500 000	500	0,1 %
100 000	5 000 000 000	50 000	0,001 %

La constante no cambia la forma. n²/2 y n² crecen igual: el doble de datos, cuatro veces el trabajo. Una constante es como una máquina más lenta: cambia los segundos, pero no lo que pasa cuando los datos se duplican. Y ya sabes que los segundos mienten.

Así, Big-O conserva solo el término que más rápido crece, sin el número que lo acompaña: 3n + 5 es O(n), n²/2 − n/2 es O(n²), 2n log n + 7n es O(n log n).

Más precisamente, para curiosos

La definición exacta: f(n) es O(g(n)) si existe una constante c y un umbral n₀ tales que f(n) ≤ c · g(n) para todo n ≥ n₀. Es decir, a partir de cierto n, f no crece más rápido que g, salvo una constante. Así, O(n) también es O(n²) (es una cota superior), pero decimos la más ajustada. También existen Θ (exactamente tanto) y Ω (al menos tanto). En conversaciones y entrevistas «O(n)» suele significar Θ(n).

La base del logaritmo tampoco se escribe: log₂ n y log₁₀ n se diferencian por una constante (log₂ n ≈ 3,32 · log₁₀ n).

Míralo

Las seis curvas en el navegador

Ejecuta las seis funciones en Bench. El eje es logarítmico: cada marca es ×10. O(n) es una recta, O(n²) es el doble de empinada y O(2ⁿ) despega enseguida.

El primer precio O(1)
Búsqueda binaria O(log n)
La suma de los precios O(n)
Ordenar (merge sort) O(n log n)
Cada par de pedidos O(n²)
Cada combinación dentro del presupuesto O(2ⁿ)

Algoritmo	n = 10	n = 1000	n = 100.000
El primer precio	1	1	1
Búsqueda binaria	4	10	17
La suma de los precios	10	1000	100.000
Ordenar (merge sort)	21	8709	1.536.371
Cada par de pedidos	45	499.500	≈ 4.995.000.000
Cada combinación dentro del presupuesto	1024	≈ 10³⁰¹	≈ 10³⁰¹⁰²

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

La respuesta para el millón de productos: el primer precio, la búsqueda, la suma y la ordenación aguantarán. Los pagos dobles pasan a ser 500 mil millones de pasos y tienen que pasar al conjunto de la lección anterior. Y todas las combinaciones de un millón de productos no se pueden listar en ninguna computadora: 2 elevado a un millón es un número de 301 030 dígitos.

Más precisamente, para curiosos

Qué usa la ordenación integrada en cada lenguaje. Array.Sort es introsort: quicksort que cambia a heapsort si la recursión se hace demasiado profunda, y a ordenación por inserción para las partes pequeñas. O(n log n) en el peor caso. Bench cuenta las comparaciones de merge sort, porque la integrada no se puede contar desde fuera. La clase es la misma.

Pruébalo

Predice la salida

El bucle exterior se ejecuta n = 8 veces. El interior divide a la mitad hasta que no queda nada. ¿Qué imprime el programa?

int n = 8;
int steps = 0;
for (int i = 0; i < n; i++)
{
    for (int left = n; left > 0; left /= 2)
    {
        steps++;
    }
}
Console.WriteLine(steps);

Respuesta

Pruébalo

Encuentra el bucle oculto

El método cuenta los clientes distintos en los pedidos del mes. Solo tiene un bucle, y aun así con 100 000 pedidos es tan lento como el informe de pagos dobles:

static int UniqueCustomers(int[] orders)
{
    var seen = new List<int>();
    foreach (int customer in orders)
    {
        if (!seen.Contains(customer))
        {
            seen.Add(customer);
        }
    }
    return seen.Count;
}

int[] orders = { 7, 3, 7, 12, 3, 7 };
Console.WriteLine(UniqueCustomers(orders));

¿En qué línea se esconde el segundo bucle?

Elige la línea con el error.

Ejercicio

Cuántas combinaciones

Resuelve la tarea en tu editor.

Los pasos de las combinaciones. Añade un contador steps a Combos: un paso por cada combinación terminada (cuando i llega al final). Ejecútalo con 10, 11 y 12 productos con precios de 500 + 100 · k centavos y un presupuesto de 5000, e imprime los pasos:

10 productos: 1024 pasos
11 productos: 2048 pasos
12 productos: 4096 pasos

Cada producto duplica los pasos. ¿Cuántos hay con 20 productos? ¿Y con 40? Calcúlalo antes de ejecutarlo.

Más tareas

La clase de cada función. Escribe el Big-O de cada función de la lección «Complejidad en tiempo: contar pasos», incluidas las ventas por producto (50 productos × n pedidos).
Búsqueda binaria con contador. Añade un contador a IndexOf y busca un precio que no está en 1000 y en 100 000 precios ordenados. Compara con el programa que divide a la mitad.
Otra vez un conjunto. Arregla el conteo de clientes distintos con un conjunto y compara los pasos con 1000 clientes distintos.

Test

Ponte a prueba

1. Una función hace 3n + 5 pasos. ¿Qué complejidad tiene?O(n)O(1)O(3n + 5)

2. Un algoritmo es O(n²). Los datos se hacen 10 veces mayores. ¿Cuánto más trabajo debes esperar?Unas 20 veces más10 veces másUnas 100 veces más

3. ¿Cuántas comprobaciones hace la búsqueda binaria en una lista ordenada de 1 000 000 de precios cuando el precio no está?Unas 500 000Unas 20Unas 1000

4. Las combinaciones dentro del presupuesto son O(2ⁿ). ¿Cuántas hay con 30 productos?Más de mil millones60Unas 900

5. Dos algoritmos para la misma tarea: uno es O(n log n), el otro O(n²). Con 10 elementos el segundo es más rápido. ¿Cuál eliges para 1 000 000 de pedidos?Da igualO(n²), porque es más rápidoO(n log n): con una n grande decide la curva, no las constantes

Big-O: cómo crece el trabajo

Cookies