Exercicis d'algorismes i complexitat

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

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

Comprovació: $2^{3} = 8$, que encara no arriba a $16$, 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 $16$ 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 $80$:

$\sum_{i=1}^{80} i = \frac{80\cdot81}{2} = 3240$

Per què no és $6400$. «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 recompte.

$\binom{22}{2} = \frac{22\cdot21}{2} = 231$

El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens $22\cdot21 = 462$, 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 $22$ a $44$ elements multiplica la feina aproximadament per quatre, no per dos.

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

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

Comprovació: $2^{4} = 16$, que encara no arriba a $32$, 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 $32$ 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 $100$:

$\sum_{i=1}^{100} i = \frac{100\cdot101}{2} = 5050$

Per què no és $10000$. «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 recompte.

$\binom{25}{2} = \frac{25\cdot24}{2} = 300$

El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens $25\cdot24 = 600$, 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 $25$ a $50$ elements multiplica la feina aproximadament per quatre, no per dos.

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

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

Comprovació: $2^{7} = 128$, que encara no arriba a $256$, 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 $256$ 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 $150$:

$\sum_{i=1}^{150} i = \frac{150\cdot151}{2} = 11325$

Per què no és $22500$. «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 recompte.

$\binom{28}{2} = \frac{28\cdot27}{2} = 378$

El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens $28\cdot27 = 756$, 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 $28$ a $56$ elements multiplica la feina aproximadament per quatre, no per dos.

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

$k = \lceil \log_2 4096\rceil = 12$

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

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