Simulacre d'examen d'algorismes i complexitat

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 cas: Ordenació per fusió.

La resposta és $n\log n$, perquè hi ha tants nivells com el logaritme i a cada nivell es fa treball lineal.

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 cas: Provar totes les combinacions de sí o no per a $n$ objectes.

La resposta és Exponencial, perquè cada objecte duplica el nombre de casos.

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 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 cas: Generar tots els subconjunts d'un conjunt de $n$ elements.

La resposta és Exponencial, perquè n'hi ha $2^{n}$.

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 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 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 cas: Inserir en una taula de dispersió ben dimensionada.

La resposta és Lineal, perquè el cost mitjà per operació és constant, o sigui lineal per a $n$ insercions.

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 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 $10$:

$\sum_{i=1}^{10} i = \frac{10\cdot11}{2} = 55$

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

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 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.