Exercicis d'algorismes i complexitat

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

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

Comprovació: $2^{3} = 8$, que encara no arriba a $10$, i $2^{4} = 16$, que ja hi arriba o el supera.

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

$\sum_{i=1}^{5} i = \frac{5\cdot6}{2} = 15$

Per què no és $25$. «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 binària en una taula ordenada.

La resposta és Logarítmic, perquè cada comparació descarta la meitat de l'interval.

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{4}{2} = \frac{4\cdot3}{2} = 6$

El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens $4\cdot3 = 12$, 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 $4$ a $8$ 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 2 = 1$, o sigui

$T(2) = 2\cdot1 = 2$

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

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

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

$k = \lceil \log_2 20\rceil = 5$

Comprovació: $2^{4} = 16$, que encara no arriba a $20$, i $2^{5} = 32$, que ja hi arriba o el supera.

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

$\sum_{i=1}^{6} i = \frac{6\cdot7}{2} = 21$

Per què no és $36$. «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 una llista i sumar-ne els elements.

La resposta és Lineal, perquè es visita cada element una sola vegada.

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

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

$T(4) = 4\cdot2 = 8$

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

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