Exercicis d'algorismes i complexitat

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

$k = \lceil \log_2 200\rceil = 8$

Comprovació: $2^{7} = 128$, que encara no arriba a $200$, i $2^{8} = 256$, que ja hi arriba o el supera.

El cost és $O(\log n)$, en el model d'operacions unitàries. Si $200$ 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 $12$:

$\sum_{i=1}^{12} i = \frac{12\cdot13}{2} = 78$

Per què no és $144$. «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: Cerca en amplada amb llistes d'adjacència.

La resposta és Lineal, perquè cada vèrtex i cada aresta es visiten un nombre constant de vegades.

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{10}{2} = \frac{10\cdot9}{2} = 45$

El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens $10\cdot9 = 90$, 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 $10$ a $20$ 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 128 = 7$, o sigui

$T(128) = 128\cdot7 = 896$

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

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

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

$k = \lceil \log_2 300\rceil = 9$

Comprovació: $2^{8} = 256$, que encara no arriba a $300$, i $2^{9} = 512$, que ja hi arriba o el supera.

El cost és $O(\log n)$, en el model d'operacions unitàries. Si $300$ 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 $15$:

$\sum_{i=1}^{15} i = \frac{15\cdot16}{2} = 120$

Per què no és $225$. «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: Duplicar un comptador fins a superar $n$.

La resposta és Logarítmic, perquè el nombre de duplicacions és el logaritme.

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{11}{2} = \frac{11\cdot10}{2} = 55$

El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens $11\cdot10 = 110$, 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 $11$ a $22$ 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 256 = 8$, o sigui

$T(256) = 256\cdot8 = 2048$

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

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