Exercicis d'algorismes i complexitat

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

$k = \lceil \log_2 1000\rceil = 10$

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

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

$\sum_{i=1}^{25} i = \frac{25\cdot26}{2} = 325$

Per què no és $625$. «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: Ordenació ràpida en el cas mitjà.

La resposta és $n\log n$, perquè la partició és lineal i la profunditat és logarítmica de mitjana.

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{14}{2} = \frac{14\cdot13}{2} = 91$

El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens $14\cdot13 = 182$, 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 $14$ a $28$ 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 2048 = 11$, o sigui

$T(2048) = 2048\cdot11 = 22528$

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

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

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

$k = \lceil \log_2 1024\rceil = 10$

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

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

$\sum_{i=1}^{30} i = \frac{30\cdot31}{2} = 465$

Per què no és $900$. «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: Multiplicar dues matrius $n\times n$ amb l'algorisme directe.

La resposta és Exponencial, perquè calen $n^{3}$ productes, que creix més de pressa que qualsevol quadrat però no és 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{15}{2} = \frac{15\cdot14}{2} = 105$

El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens $15\cdot14 = 210$, 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 $15$ a $30$ 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 4096 = 12$, o sigui

$T(4096) = 4096\cdot12 = 49152$

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

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