Cuánto cuesta de verdad

Dos programas que funcionan pueden tardar horas de diferencia.

1Por qué

«Funciona» no es suficiente. Dos programas que dan la misma respuesta pueden tardar un segundo y una tarde, y con los datos de prueba —cinco números— los dos parecen instantáneos. El problema aparece cuando llegan cincuenta mil.

Para saberlo no hace falta un cronómetro: se cuenta. Cada vez que el algoritmo mira un par de datos, se suma uno. Ese número no depende de tu máquina ni de si tienes el navegador abierto, y por eso es lo que se compara.

El ordenamiento de la lección anterior tiene un ciclo dentro de otro. El de fuera da unas n vueltas, y el de dentro otras tantas por cada una: el trabajo no crece con n, crece con n por n.

Eso se ve solo al medirlo. Con 4 datos son 6 comparaciones; con 8, veintiocho; con 16, ciento veinte. Cada vez que el tamaño se dobla, el trabajo se cuadruplica. Un algoritmo así se llama cuadrático, y por eso ordenar un millón de datos con este método no es lento: es imposible.

Compáralo con recorrer la lista una vez, que es n a secas: doblar el tamaño solo dobla el trabajo. La diferencia entre esas dos formas de crecer es la mitad de lo que un ramo de algoritmos viene a enseñar.

2Míralo andar

Este programa funciona. Léelo, y después ejecútalo sin cambiar nada.

#include <stdio.h>
 
int lineal(int n)
{
    int cuenta = 0;
    for (int i = 0; i < n; i++)
        cuenta = cuenta + 1;
    return cuenta;
}
 
int cuadratico(int n)
{
    int cuenta = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            cuenta = cuenta + 1;
    return cuenta;
}
 
int main(void)
{
    printf("%d %d\n", lineal(4), cuadratico(4));
    printf("%d %d\n", lineal(8), cuadratico(8));
    printf("%d %d\n", lineal(16), cuadratico(16));
    return 0;
}

línea 6
Un solo ciclo: el trabajo va al mismo ritmo que el tamaño.
línea 14
Un ciclo dentro de otro. Es la forma del ordenamiento de la lección anterior, sin el ordenar.
línea 22
Mira las tres líneas al ejecutar: el de la izquierda se dobla, el de la derecha se cuadruplica.

3Ahora tú

A cuadratico le falta contar. Escribe la línea, para que salga 4 6, después 8 28 y después 16 120

#include <stdio.h>
 
int lineal(int n)
{
    int cuenta = 0;
    for (int i = 0; i < n; i++)
        cuenta = cuenta + 1;
    return cuenta;
}
 
int cuadratico(int n)
{
    int cuenta = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            
    return cuenta;
}
 
int main(void)
{
    printf("%d %d\n", lineal(4), cuadratico(4));
    printf("%d %d\n", lineal(8), cuadratico(8));
    printf("%d %d\n", lineal(16), cuadratico(16));
    return 0;
}

↖︎ Tu línea va aquí: lo que se hace una vez por cada par mirado.

Ejecutar

Lo que dice tu programa

↖︎ Escribe tu parte y dale a Ejecutar

Qué pasó

Aquí te aviso si tu programa hace algo raro.

Más adelante vas a ver dónde guarda el computador cada cosa. Todavía no hace falta.