Exercicis d'algorismes i complexitat

El raonament. Després de $k$ duplicacions, $x = 2^{k}$. La condició de sortida és $2^{k} \geq 1500$, o sigui

$k = \lceil \log_2 1500\rceil = 11$

Comprovació: $2^{10} = 1024$, que encara no arriba a $1500$, i $2^{11} = 2048$, que ja hi arriba o el supera.

El cost és $O(\log n)$, en el model d'operacions unitàries. Si $1500$ fos astronòmic, el número $x$ tindria molts bits i cada duplicació ja no seria de cost constant: en complexitat de bits el cost pujaria. Declarar el model no és un formalisme.

El compte correcte. El bucle interior fa $1$ pas la primera vegada, $2$ la segona, i així fins a $35$:

$\sum_{i=1}^{35} i = \frac{35\cdot36}{2} = 630$

Per què no és $1225$. «Dos bucles niats» no és una unitat d'anàlisi: el que compta és quantes iteracions fa cadascun realment. Aquí el total és aproximadament la meitat del quadrat.

Asimptòticament sí que és $\Theta(n^{2})$, perquè la constant $1/2$ no canvia l'ordre. Però la constant importa a la pràctica: un factor $2$ és un factor $2$ de temps real.

El cas: Recórrer totes les permutacions de $n$ elements.

La resposta és Exponencial, perquè n'hi ha $n!$, que creix encara més de pressa que una exponencial.

Com es raona en general. Compta quantes operacions elementals es fan en funció de la mida de l'entrada. Si cada pas divideix el problema per una constant, el cost és logarítmic; si cada element es toca un nombre constant de vegades, és lineal; si per a cada element se'n recorren tots els altres, és quadràtic; i si cada element duplica el nombre de casos a explorar, és exponencial.

L'avís de sempre: aquests ordres no diuen res sobre el temps real sense fixar un model de màquina, i les constants amagades poden decidir la comparació per a les mides que faràs servir de veritat.

El recompte.

$\binom{16}{2} = \frac{16\cdot15}{2} = 120$

El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens $16\cdot15 = 240$, però cada parella hi surt dues vegades (un cop en cada ordre). Dividint per dos queda el nombre real de parelles.

El que en diu l'asimptòtica. Aquest recompte és $\Theta(n^{2})$, i per això els algorismes que comparen tothom amb tothom es fan impracticables de pressa: passar de $16$ a $32$ elements multiplica la feina aproximadament per quatre, no per dos.

La solució de la recurrència. Dividint per $n$ i posant $S(k) = T(2^{k})/2^{k}$ queda $S(k) = S(k-1) + 1$, que amb $S(0) = 0$ dona $S(k) = k$. Desfent el canvi,

$T(n) = n\log_2 n$

Aquí: $\log_2 8192 = 13$, o sigui

$T(8192) = 8192\cdot13 = 106496$

La interpretació. Hi ha $13$ nivells de recursió (cada un parteix el problema per la meitat) i a cada nivell el treball total de combinar és lineal, o sigui $8192$. Multiplicant surt el cost.

Compara-ho amb un algorisme quadràtic, que per a $8192$ elements faria uns $67108864$ passos: la diferència és de 630 vegades.

El raonament. Després de $k$ duplicacions, $x = 2^{k}$. La condició de sortida és $2^{k} \geq 2000$, o sigui

$k = \lceil \log_2 2000\rceil = 11$

Comprovació: $2^{10} = 1024$, que encara no arriba a $2000$, i $2^{11} = 2048$, que ja hi arriba o el supera.

El cost és $O(\log n)$, en el model d'operacions unitàries. Si $2000$ fos astronòmic, el número $x$ tindria molts bits i cada duplicació ja no seria de cost constant: en complexitat de bits el cost pujaria. Declarar el model no és un formalisme.

El compte correcte. El bucle interior fa $1$ pas la primera vegada, $2$ la segona, i així fins a $40$:

$\sum_{i=1}^{40} i = \frac{40\cdot41}{2} = 820$

Per què no és $1600$. «Dos bucles niats» no és una unitat d'anàlisi: el que compta és quantes iteracions fa cadascun realment. Aquí el total és aproximadament la meitat del quadrat.

Asimptòticament sí que és $\Theta(n^{2})$, perquè la constant $1/2$ no canvia l'ordre. Però la constant importa a la pràctica: un factor $2$ és un factor $2$ de temps real.

El cas: Comprovar si un element és en una llista no ordenada.

La resposta és Lineal, perquè en el cas pitjor cal mirar-los tots.

Com es raona en general. Compta quantes operacions elementals es fan en funció de la mida de l'entrada. Si cada pas divideix el problema per una constant, el cost és logarítmic; si cada element es toca un nombre constant de vegades, és lineal; si per a cada element se'n recorren tots els altres, és quadràtic; i si cada element duplica el nombre de casos a explorar, és exponencial.

L'avís de sempre: aquests ordres no diuen res sobre el temps real sense fixar un model de màquina, i les constants amagades poden decidir la comparació per a les mides que faràs servir de veritat.

El recompte.

$\binom{17}{2} = \frac{17\cdot16}{2} = 136$

El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens $17\cdot16 = 272$, però cada parella hi surt dues vegades (un cop en cada ordre). Dividint per dos queda el nombre real de parelles.

El que en diu l'asimptòtica. Aquest recompte és $\Theta(n^{2})$, i per això els algorismes que comparen tothom amb tothom es fan impracticables de pressa: passar de $17$ a $34$ elements multiplica la feina aproximadament per quatre, no per dos.

La solució de la recurrència. Dividint per $n$ i posant $S(k) = T(2^{k})/2^{k}$ queda $S(k) = S(k-1) + 1$, que amb $S(0) = 0$ dona $S(k) = k$. Desfent el canvi,

$T(n) = n\log_2 n$

Aquí: $\log_2 16384 = 14$, o sigui

$T(16384) = 16384\cdot14 = 229376$

La interpretació. Hi ha $14$ nivells de recursió (cada un parteix el problema per la meitat) i a cada nivell el treball total de combinar és lineal, o sigui $16384$. Multiplicant surt el cost.

Compara-ho amb un algorisme quadràtic, que per a $16384$ elements faria uns $268435456$ passos: la diferència és de 1170 vegades.