Cost d'algorismes

Per què?

Tens dos programes que resolen el mateix problema. Amb l’exemple de l’enunciat, tots dos responen a l’instant. Amb les dades reals (un milió d’elements), un triga una dècima de segon i l’altre tres hores. Al Jutge, el segon dona «temps límit excedit».

Cronometrar no és una bona manera de saber-ho abans: depèn de l’ordinador, del compilador i de l’exemple que provis. El que necessites és una manera de predir com creix el temps quan creixen les dades. Això és el cost d’un algorisme.

La idea: comptar i quedar-se amb el que creix més

Per analitzar un algorisme:

1. Decideix què és la mida de l’entrada, $n$: el nombre d’elements d’un vector, d’una llista o d’un arbre; el valor d’un número; el nombre de dígits…
2. Compta quantes operacions elementals fa en funció de $n$. Una operació elemental és qualsevol cosa que costa sempre el mateix: una assignació d’un int, una suma, una comparació, accedir a v[i], un push d’una pila…
3. Mira el cas pitjor: l’entrada de mida $n$ que fa treballar més l’algorisme. (Una cerca on l’element no hi és, per exemple.)
4. Queda’t amb el terme que creix més ràpid i oblida les constants.

Per què oblidar les constants? Perquè depenen de la màquina i del compilador, i perquè quan $n$ és gran, el terme dominant ho decideix tot. Si un algorisme fa $3n^2 + 100n + 5000$ operacions, amb $n = 10^6$ el $3n^2$ són $3 \cdot 10^{12}$, i la resta, uns $10^8$: menys d’una deumil·lèsima part. Diem que el cost és $\Theta(n^2)$.

Prova-ho a l’eina «Com creix el cost» de dalt de tot: compara les funcions per a $n$ cada vegada més grans.

La notació asimptòtica

Per dir «creix com $n^2$» amb precisió hi ha tres notacions. Si $f(n)$ és el nombre d’operacions i $g(n)$ una funció de referència:

Per exemple, $3n^2 + 100n + 5000 \in \Theta(n^2)$, i també és $O(n^3)$ (és cert, però no és la millor fita) i $\Omega(n)$. Per veure que és $O(n^2)$, n’hi ha prou de trobar unes constants: amb $c = 4$ i $n_0 = 200$, $3n^2 + 100n + 5000 \le 4n^2$, perquè per a $n \ge 200$ ja tens $n^2 \ge 100n + 5000$. I és $\Omega(n^2)$ amb $c = 3$ i $n_0 = 1$.

A PRO2 fem servir sobretot $\Theta$: diu el cost exacte, llevat de constants.

Unes quantes regles que es fan servir sempre:

• Les constants no compten: $\Theta(5n) = \Theta(n)$.
• En una suma, guanya el terme més gran: $\Theta(n^2 + n \log n) = \Theta(n^2)$.
• La base dels logaritmes no compta (canviar de base és multiplicar per una constant): $\Theta(\log_2 n) = \Theta(\log_{10} n)$, i s’escriu $\Theta(\log n)$.

Els ordres de creixement habituals

(Els temps suposen uns $10^8$ passos per segon, que és un ordre de magnitud raonable.)

La lliçó: la diferència entre ordres és enorme, i cap millora de constants ni cap ordinador més ràpid no la compensa. Passar d’un algorisme $\Theta(n^2)$ a un de $\Theta(n \log n)$ val més que un ordinador mil vegades més ràpid.

Com es calcula el cost

Seqüència

Si fas una cosa que costa $C_1$ i després una altra que costa $C_2$, el total és $C_1 + C_2$. En notació $\Theta$, això és el més gran dels dos: $\Theta(n) + \Theta(n^2) = \Theta(n^2)$.

Condicional

if (B) S1; else S2; costa el que costa avaluar B més, en el cas pitjor, el més car de S1 i S2.

Bucle

Suma el cost de cada volta. Si totes costen el mateix, és nombre de voltes × cost d’una volta.

for (int i = 0; i < n; ++i) s += v[i];   // n voltes de Θ(1): Θ(n)

Amb bucles niuats, el de dins s’executa sencer a cada volta del de fora:

for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) ...      // n · n voltes: Θ(n²)

Si el de dins depèn del de fora, cal sumar:

for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j) ...      // 0 + 1 + ... + (n-1) = n(n-1)/2: Θ(n²)

I si la variable del bucle es multiplica o es divideix, en lloc de sumar-se, el nombre de voltes és logarítmic:

for (int i = 1; i < n; i *= 2) ...       // i = 1, 2, 4, 8, ...: unes log₂ n voltes, Θ(log n)

Crides a funcions i operacions

Una crida costa el que costa la funció cridada amb aquells paràmetres. Compte amb les operacions que semblen elementals però no ho són:

Un exemple: tots diferents

Vols saber si tots els elements d’un vector són diferents. La manera directa: comparar cada element amb tots els que té a la dreta.

// Pre: cert. Post: retorna si tots els elements de v són diferents.
bool tots_diferents(const vector<int>& v) {
    int n = v.size();
    bool dif = true;
    int i = 0;
    while (i < n and dif) {
        int j = i + 1;
        while (j < n and dif) {
            if (v[i] == v[j]) dif = false;
            ++j;
        }
        ++i;
    }
    return dif;
}

Cas pitjor: quan tots són diferents (no s’atura mai abans). El bucle de dins fa $n - 1 - i$ voltes per a cada $i$: en total $(n-1) + (n-2) + \dots + 0 = \frac{n(n-1)}{2}$. Cost $\Theta(n^2)$.

Amb un set, cada element es busca entre els que ja s’han vist en $\Theta(\log n)$:

bool tots_diferents(const vector<int>& v) {
    set<int> vistos;
    bool dif = true;
    int i = 0;
    while (i < int(v.size()) and dif) {
        if (vistos.count(v[i]) == 1) dif = false;
        else vistos.insert(v[i]);
        ++i;
    }
    return dif;
}

$n$ voltes de $\Theta(\log n)$: $\Theta(n \log n)$. (Una altra opció amb el mateix cost: ordenar una còpia i mirar si hi ha dos consecutius iguals.)

Errors habituals

Exercicis

// a)
for (int i = 0; i < n; ++i)
    for (int j = 0; j < 10; ++j) ...

// b)
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < n; ++j) ...

// c)
for (int i = 0; i < n; ++i)
    for (int j = i; j < n; ++j) ...

// d)
int k = n;
while (k > 1) k /= 3;

// e)
for (int i = 0; i < n; ++i)
    for (int j = 1; j < n; j *= 2) ...

// a)
int f(vector<int> v) { return v[0]; }

// b)
bool g(const list<int>& l, int x) {
    for (int y : l) if (y == x) return true;
    return false;
}

// c)
void h(vector<int>& v) {
    while (not v.empty()) v.erase(v.begin());
}

// d)
int k(const map<string, int>& m, const vector<string>& claus) {
    int s = 0;
    for (const string& c : claus) s += m.at(c);
    return s;
}

// Pre: cert. Post: retorna si tots els elements de v són diferents.
bool tots_diferents(const vector<int>& v) {
    vector<int> w = v;                     // còpia: Θ(n)
    sort(w.begin(), w.end());              // ordenar: Θ(n log n)
    bool dif = true;
    int i = 1;
    // Inv: 1 <= i, dif = (w[0..i-1] no té dos consecutius iguals)
    while (i < int(w.size()) and dif) {    // com a molt n - 1 voltes de Θ(1): Θ(n)
        if (w[i - 1] == w[i]) dif = false;
        ++i;
    }
    return dif;
}