Esercizio - algoritmo ibrido con soglia ottima e confronto con la versione ricorsiva (compito del 4 settembre 2024, es. 1)

Teoria usata: Albero della ricorrenza e formula generale per le ricorrenzeL'albero della ricorrenza ha la forma dell'albero delle chiamate dell'istanza peggiore e T(n) è la somma dei lavori dei nodi. Per la famiglia T(n) = s(n)T(f(n)) + w(n) con base T0 per n <= n0, contando i nodi per livello con le iterate di f e il livello f*(n,n0) si ottiene la formula chiusa T(n) = somma_l [prodotto_j s(f^(j)(n))] w(f^(l)(n)) + [prodotto s] T0, verificata per induzione e applicata a esempi (merge sort, Hanoi, ricorrenze con radice).Albero della ricorrenza e formula generale per le ricorrenze → (formula generale con taglia di base $n_0$), Master Theorem - enunciato, casi e applicazioniMaster Theorem per T(n) = aT(n/b) + w(n): si confronta w(n) con la funzione soglia n^(log_b a). Caso 1 (w minore di una potenza polinomiale): Theta(n^(log_b a)); caso 2 (w della stessa taglia): Theta(n^(log_b a) log n); caso 3 (w maggiore e regolare): Theta(w(n)). Prova completa dai livelli dell'albero, versione estesa (parti intere, n0 qualsiasi), esempi, e l'uso scorretto quando nessun caso si applica (w = n log n).Master Theorem - enunciato, casi e applicazioni →. Stessa struttura dell'esercizio Esercizio - algoritmo ibrido e valore ottimo della soglia (compito del 27 gennaio 2025, es. 1), con costanti diverse e un'ottimizzazione più semplice.

(a) Pseudocodice di $H$

Si modifica il caso base di $A_1$: sotto la soglia si passa a $A_2$. $A_1$ genera quattro sottoistanze di taglia $n/2$ (da $s(n) = 4$, $f(n) = n/2$) e il suo lavoro per istanza è $128n$.

H(i, n0)                                      {n0 potenza di due, costante}
n <- size(i)
[B]: if n <= n0 then return A2(i)             // costo 2 n^3
[D]: <i_1, ..., i_4> <- A_D(i)                // Divide di A1: quattro sottoistanze di taglia n/2
[R]: for j <- 1 to 4 do s_j <- H(i_j, n0)
[C]: return A_C(s_1, ..., s_4)                // Conquer di A1

(Il codice è quello di $A_1$ con le chiamate ricorsive a $H$, passando sempre lo stesso $n_0$.)

(b) La ricorrenza parametrica e la sua soluzione

Per $n$ e $n_0 \le n$ potenze di due: $$T_H(n, n_0) = \begin{cases} 2n^3 & n \le n_0 \\ 4\,T_H(n/2,\, n_0) + 128\,n & n > n_0. \end{cases}$$ Formula generale con $s(n) = 4$, $w(n) = 128n$, $f(n) = n/2$, costo di base $T_0 = 2n_0^3$ (le foglie hanno taglia $n_0$). Con $m = \log_2(n/n_0)$ si ha $f^\ast(n, n_0) = m - 1$: i livelli non di base sono $0, \dots, m-1$, le foglie sono al livello $m$. Al livello $\ell$ ci sono $4^\ell$ nodi, ciascuno di lavoro $128\cdot\frac n{2^\ell}$, quindi il livello costa $4^\ell\cdot 128\frac{n}{2^\ell} = 128\,n\,2^\ell$. Le foglie sono $4^m$: $$\begin{aligned} T_H(n, n_0) &= \sum_{\ell=0}^{m-1} 128\,n\,2^\ell + 4^{m}\cdot 2n_0^3 = 128\,n\,(2^m - 1) + 2\left(\frac{n}{n_0}\right)^2 n_0^3 \\ &= 128\,n\left(\frac{n}{n_0} - 1\right) + 2\,n^2\,n_0 , \end{aligned}$$ dove si sono usati $\sum_{\ell=0}^{m-1}2^\ell = 2^m - 1$, $2^m = n/n_0$ e $4^m = (2^m)^2 = (n/n_0)^2$. Sviluppando: $$T_H(n, n_0) = \frac{128\,n^2}{n_0} - 128\,n + 2\,n^2\,n_0 \qquad (n \ge n_0).$$ Verifica per induzione sul numero di livelli (omessa nel testo): il caso $n = n_0$ dà $128 n\cdot 0 + 2n^3 = 2n^3$ ✓; il passo $4\,T_H(n/2, n_0) + 128n = 4\left[128\frac n2\left(\frac{n}{2n_0} - 1\right) + 2\frac{n^2}{4}n_0\right] + 128n = 128n\left(\frac n{n_0} - 2\right) + 2n^2n_0 + 128n = 128n\left(\frac{n}{n_0} - 1\right) + 2n^2n_0$ ✓. Con Python, per $n = 2^k$ ($k \le 14$) e ogni $n_0 = 2^j \le n$ la ricorrenza coincide con la formula.

(c) La soglia ottima

Per $n$ fisso si minimizza rispetto a $n_0$ (trattato come reale) $F(n_0) = \frac{128\,n^2}{n_0} + 2n^2 n_0 - 128n$: $$\frac{\partial T_H}{\partial n_0} = -\frac{128\,n^2}{n_0^2} + 2n^2 \overset{?}{<} 0 \iff 2n^2 < \frac{128\,n^2}{n_0^2} \iff n_0^2 < 64 \iff n_0 < 8.$$ Quindi $T_H$ decresce per $n_0 < 8$ e cresce per $n_0 > 8$ (indipendentemente da $n$): il minimo è in $\bar n_0 = 8$, che è già una potenza di due. Valore: $$T_H(n, 8) = \frac{128\,n^2}{8} - 128\,n + 16\,n^2 = 32\,n^2 - 128\,n \qquad (n \ge 8).$$

Confronto con $A_1$. $A_1$ coincide con $H$ per $n_0 = 1$ (per $n = 1$ vale $2\cdot1^3 = 2 = T_{A_1}(1)$): $T_{A_1}(n) = T_H(n, 1) = 128n^2 - 128n + 2n^2 = 130\,n^2 - 128\,n$. Il rapporto è $$\frac{T_{A_1}(n)}{T_H(n, 8)} = \frac{130\,n^2 - 128\,n}{32\,n^2 - 128\,n} \longrightarrow \frac{130}{32} \approx 4{,}06,$$ quindi per $n \ge 8$ l'ibrido è più di quattro volte più veloce (per $n = 8$: $7296$ contro $1024$, cioè $7{,}1$ volte; il valore $1024 = 2\cdot8^3$ è il costo di $A_2$ stesso).

Perché proprio $8$. Confronto locale tra risolvere direttamente con $A_2$ e fare un passo di ricorsione per poi usare $A_2$ sulle quattro metà: per $n = 8$, $A_2$ costa $2\cdot 8^3 = 1024$ e un passo di ricorsione $4\cdot 2\cdot 4^3 + 128\cdot 8 = 512 + 1024 = 1536$: conviene $A_2$. Per $n = 16$, $A_2$ costa $2\cdot16^3 = 8192$ e un passo di ricorsione $4\cdot 2\cdot 8^3 + 128\cdot 16 = 4096 + 2048 = 6144$: conviene ricorrere. La soglia sta quindi tra $8$ e $16$, e si ferma la ricorsione a $n_0 = 8$.

Osservazione. Il costo $F(n_0)/n^2 = \frac{128}{n_0} + 2n_0$ è simmetrico rispetto a $n_0 \mapsto 64/n_0$: per esempio $n_0 = 4$ e $n_0 = 16$ danno lo stesso costo, $T_H = 40\,n^2 - 128\,n$ (verificato), peggiore di $32n^2 - 128n$.

from functools import lru_cache

@lru_cache(None)
def TH(n, n0):
    return 2 * n**3 if n <= n0 else 4 * TH(n // 2, n0) + 128 * n

n = 2**12
print({2**j: TH(n, 2**j) for j in range(0, 8)})
assert min(range(13), key=lambda j: TH(n, 2**j)) == 3                  # n0 = 8
assert all(TH(2**k, 8) == 32 * 4**k - 128 * 2**k for k in range(3, 20))
assert all(TH(2**k, 1) == 130 * 4**k - 128 * 2**k for k in range(0, 20))