Esercizio 5crescita delle funzioni e costo degli algoritmi

1. $f(n)$

Si guarda il termine che cresce più in fretta e si trascurano costanti e termini di ordine inferiore:

• $\log n$ cresce lentamente;
• $2n\log(n+4) \sim 2n\log n$: $n\log n$;
• $\dfrac{(3n+1)(n-1)}{n^2} = \dfrac{3n^2 - 2n - 1}{n^2} \to 3$: una costante.

Quindi $f(n) = \Theta(n\log n)$. Numericamente $f(n)/(n\log n)$ tende a $2$ (con $n = 10^6$ vale $2{,}000002$).

2. $T(n)$

Dominante: $n\log n$ (gli altri termini sono $3n$, $10\log\log n$ e una costante: $o(n\log n)$). Dunque:

• $\Theta(n\log n)$: vera;
• $\Omega(n)$: vera (cresce almeno come $n$);
• $O(n^2)$: vera (è un limite superiore non stretto);
• $O(n)$: falsa, perché $n\log n$ cresce più di $n$.

Un'affermazione $O(\cdot)$ è un limite superiore, non necessariamente stretto: $T(n) = O(n^2)$ è vero ma poco informativo.

3. Ordine

$\log n \ll n \ll n\log n$: $h(n),\ f(n),\ g(n)$.

4. Ordinamento per selezione

L'ordinamento per selezione fa $\dfrac{n(n-1)}{2} = \Theta(n^2)$ confronti. Con $n \to 10n$ il tempo si moltiplica per $\approx 10^2 = 100$ (esattamente $100{,}009$): $10\ \text{s} \times 100 \approx$ 1000 secondi. (Con mergesort, $\Theta(n\log n)$, il fattore sarebbe circa $12{,}5$.)

5. $A_0$ e $A_1$

$A_1(n) = n^2 - 1000n + 7n = n^2 - 993n$: per $n$ grande il rapporto $A_1/A_0 \to 1/5$ ($0{,}1998$ per $n = 10^5$; $0{,}0014$ per $n = 10^3$, dove il termine $-1000n$ pesa). Entrambi sono $\Theta(n^2)$: dal punto di vista asintotico sono equivalenti. Le costanti ($5$ contro $1$) e i termini lineari non contano nella notazione $O$.

6. Conseguenze di $T(n) = O(n^5)$

• $T = O(n^6)$: sempre vera (un limite più largo);
• $T = O(2^n)$: sempre vera;
• $T = O(n^4)$: non è detto ($T = n^5$ la smentisce);
• $T = \Omega(n^5)$: non è detto ($T = n$ è $O(n^5)$ ma non $\Omega(n^5)$).

$O$ dà un limite dall'alto, $\Omega$ dal basso, $\Theta$ i due insieme.

7. Vettore dinamico e costo ammortizzato

Una append che trova il vettore pieno copia tutti gli $n$ elementi. Con raddoppio le copie avvengono quando $n = 1, 2, 4, 8, \dots$: in $m$ inserimenti sono $1 + 2 + 4 + \cdots < 2m$. Con incremento di 1 si copia a ogni inserimento: $1 + 2 + \cdots + (m-1) = \Theta(m^2)$.

Costo ammortizzato $O(1)$: il costo totale di $m$ operazioni è $O(m)$ ($< 2m$ copie più $m$ scritture), cioè $O(1)$ per operazione in media sulla sequenza, anche se una singola operazione può costare $O(n)$. Non è una media su input casuali: vale nel caso peggiore, per qualsiasi sequenza. Un incremento costante non basta: il totale resta quadratico.

8. Coda su lista

pop(0) rimuove il primo elemento e sposta tutti gli altri di un posto: $O(n)$. Svuotare una lista di $n$ elementi costa $(n-1) + (n-2) + \cdots = \Theta(n^2)$ spostamenti ($499\,500$ per $n = 1000$, $\approx 2\cdot 10^6$ per $n = 2000$: il doppio dei dati, quattro volte il lavoro). deque.popleft() è $O(1)$ e svuotare la coda costa $\Theta(n)$ (Pila e codaPila (LIFO) e coda (FIFO) come ADT: operazioni e costi; realizzazione in Python con list e collections.deque; realizzazione in C con array e indici, coda circolare; applicazioni (parentesi bilanciate, stack delle chiamate, visite).Pila e coda →).

Verifica

import math

def copie(m, nuova_cap):
    """numero di elementi copiati in m inserimenti; nuova_cap(cap) = capacità dopo la crescita"""
    cap, n, tot = 1, 0, 0
    for _ in range(m):
        if n == cap:
            tot += n
            cap = nuova_cap(cap)
        n += 1
    return tot

for m in (100, 1000, 10000):
    print(m, copie(m, lambda c: 2 * c), copie(m, lambda c: c + 1), copie(m, lambda c: c + 10), 2 * m)

f = lambda n: math.log(n) + 2 * n * math.log(n + 4) + (3 * n + 1) * (n - 1) / n ** 2
print(f(10 ** 6) / (10 ** 6 * math.log(10 ** 6)))              # 2.0000017962...

T = lambda n: 3 * n + 10 * math.log(math.log(n)) + n * math.log(n) + 8
print(T(10 ** 8) / (10 ** 8 * math.log(10 ** 8)))              # 1.1628...: tende a 1

sel = lambda n: n * (n - 1) // 2                                # confronti del selection sort
print(sel(10 ** 5) / sel(10 ** 4))                              # 100.009

A0 = lambda n: 5 * n * n
A1 = lambda n: n * (n - 1000) + 7 * n
print(A1(10 ** 7) / A0(10 ** 7))                                # 0.19998...: costante, stesso ordine

spostamenti = lambda n: sum(n - 1 - i for i in range(n))        # svuotare una lista con pop(0)
print(spostamenti(1000), spostamenti(2000))                     # 499500 1999000

Errori comuni

• Tenere le costanti o i termini di ordine inferiore nella risposta ($2n\log n$ invece di $n\log n$).
• Confondere $O$ (limite superiore) con $\Theta$ (limite stretto).
• Dire che un algoritmo "da $5n^2$" è peggiore di uno "da $n^2$": stessa classe di crescita.
• Credere che $O(1)$ ammortizzato voglia dire "veloce in media su dati casuali".
• Usare list.pop(0) per fare una coda.