Albero della ricorrenza e formula generale per le ricorrenze

Lo srotolamento di Divide and conquer - proprietà di sottostruttura e albero delle chiamateUn algoritmo divide and conquer nasce da una proprietà di sottostruttura (funzioni Divide e Conquer, base n0) con sottoistanze di taglia strettamente minore; l'albero delle chiamate ne descrive l'esecuzione, e il D&C non ha memoria (ripete le sottoistanze uguali). Esempio completo: MAX di un array, con correttezza per induzione, ricorrenza e conteggio esatto n-1 tramite il teorema sugli alberi binari pieni.Divide and conquer - proprietà di sottostruttura e albero delle chiamate → funziona caso per caso. Qui lo si organizza in una formula generale: leggendo l'albero della ricorrenza livello per livello si ricava $T(n)$ per un'intera famiglia di algoritmi D&C.

Albero delle chiamate e albero della ricorrenza

A ogni esecuzione di un algoritmo D&C corrisponde un albero delle chiamate. Quando si studia la complessità al caso peggiore con una ricorrenza, si associa l'albero della ricorrenza: ha la stessa forma dell'albero delle chiamate dell'istanza peggiore di taglia $n$, e nei nodi si scrivono:

• per un nodo interno: la taglia della sottoistanza (convenzionalmente dentro il nodo) e il costo complessivo di $A_D$ e $A_C$ su quell'istanza (di fianco);
• per una foglia: la taglia di base e il costo della risoluzione diretta.

Il costo cumulativo di Divide e Conquer per un'istanza non di base, o il costo della risoluzione diretta per una di base, si chiama lavoro (work). La complessità $T(n)$ si ottiene sommando tutti i lavori dei nodi: l'albero elenca i contributi dovuti alla gerarchia di istanze generate dall'istanza principale. Un esempio completo è l'albero per MAX in Divide and conquer - proprietà di sottostruttura e albero delle chiamateUn algoritmo divide and conquer nasce da una proprietà di sottostruttura (funzioni Divide e Conquer, base n0) con sottoistanze di taglia strettamente minore; l'albero delle chiamate ne descrive l'esecuzione, e il D&C non ha memoria (ripete le sottoistanze uguali). Esempio completo: MAX di un array, con correttezza per induzione, ricorrenza e conteggio esatto n-1 tramite il teorema sugli alberi binari pieni.Divide and conquer - proprietà di sottostruttura e albero delle chiamate →.

La famiglia di ricorrenze

Siano $s, f : \mathbb{N} \to \mathbb{N}$ e $w : \mathbb{N} \to \mathbb{R}^+ \cup \{0\}$ funzioni non decrescenti:

• $s(n)$ è il numero di sottoistanze generate da un'istanza (non di base) di taglia $n$;
• $f(n)$ è la taglia delle sottoistanze generate; deve essere una contrazione, $f(n) < n$ per ogni taglia non di base (altrimenti la ricorsione non termina);
• $w(n)$ è il lavoro (divide più conquer) di un'istanza non di base di taglia $n$; con costi unitari o nulli $w(n) \in \mathbb{N}$.

Si restringe il paradigma al caso in cui ogni istanza di taglia $n$ genera sempre $s(n)$ sottoistanze, tutte di taglia $f(n)$: il numero può dipendere da $n$ ma non dall'istanza. Le istanze di base hanno taglia $\le n_0$ e $T_0$ è un limite superiore al tempo della risoluzione diretta. Il metacodice è lo stesso di prima con $k \leftarrow s(n)$, e la ricorrenza diventa $$T(n) = \begin{cases} T_0 & n \le n_0 \\ s(n)\cdot T\bigl(f(n)\bigr) + w(n) & n > n_0, \end{cases} \tag{$\ast$}$$ con $w(n) = T_{A_D}(n) + T_{A_C}(n)$ il lavoro dell'istanza (peggiore, nell'analisi del caso peggiore) di taglia $n$.

Osservazioni. Poiché $s, f, w$ sono non decrescenti, lo è anche $T$. Se le quantità di $(\ast)$ sono solo limitazioni superiori di numero di sottoistanze, taglie o lavoro, la soluzione $T(n)$ è una limitazione superiore alla complessità.

Esempio: merge sort. Per $n = 2^k$ e con costo unitario solo per i confronti tra chiavi:

• $n_0 = 1$, $T_0 = 0$ (un solo elemento è già ordinato);
• $s(n) = 2$ (costante);
• $f(n) = n/2$; per $n$ qualsiasi si userebbe la contrazione $\lceil n/2\rceil$, che è un limite superiore di entrambe le taglie e darebbe solo una limitazione superiore;
• $w(n) = n - 1$: il Divide spezza l'insieme senza confronti, il Conquer (la fusione ordinata, Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →) richiede al caso peggiore $n - 1$ confronti.

La ricorrenza è $T(n) = 0$ per $n = 1$ e $T(n) = 2T(n/2) + n - 1$ per $n > 1$.

Le iterate di $f$

Le iterate danno le taglie delle sottoistanze ai vari livelli di ricorsione: $$f^{(0)}(n) = n, \qquad f^{(\ell)}(n) = f\bigl(f^{(\ell-1)}(n)\bigr) \quad (\ell > 0),$$ cioè $f$ applicata $\ell$ volte. Casi notevoli, per ricavare l'espressione esplicita:

(Per $\sqrt n$: $f^{(2)}(n) = (n^{1/2})^{1/2} = n^{1/2^2}$, e così via.) In presenza di parti intere l'espressione analitica di $f^{(\ell)}$ diventa molto più difficile.

Data una contrazione $f$ e un valore $n_0$ si definisce $$f^{\ast}(n, n_0) = \max\{\,k : f^{(k)}(n) > n_0\,\}.$$ È il massimo indice di iterata la cui taglia è strettamente maggiore di $n_0$, cioè l'ultimo livello di istanze non di base: alla radice (livello $0$) c'è taglia $n = f^{(0)}(n)$, al livello $1$ taglia $f(n)$, ... al livello $f^\ast(n,n_0)$ l'ultima taglia $> n_0$, e al livello $f^\ast(n, n_0) + 1$ ci sono le foglie (istanze di base). La definizione ha senso solo per $n > n_0$ (altrimenti si prenderebbe il massimo dell'insieme vuoto): per $n \le n_0$ si pone per convenzione $f^\ast(n,n_0) = -1$, in modo che l'unica foglia dell'albero (l'istanza principale, già di base) sia al livello $f^\ast + 1 = 0$.

Calcolo di $f^\ast$ nei casi notevoli:

• $n = b^k$, $f(n) = n/b$: $f^{(k)}(n) = n/b^k > n_0 \iff b^k < n/n_0 \iff k < \log_b(n/n_0)$, quindi $$f^\ast(n, n_0) = \log_b \frac{n}{n_0} - 1, \qquad f^\ast(n, 1) = \log_b n - 1$$ (con $n/n_0$ potenza di $b$, perché $k$ intero massimo strettamente minore di un intero è l'intero precedente).
• $n = 2^{2^k}$, $f(n) = \sqrt n$: $n^{1/2^k} > n_0 \iff \frac{\log_2 n}{2^k} > \log_2 n_0 \iff 2^k < \frac{\log_2 n}{\log_2 n_0} \iff k < \log_2\log_2 n - \log_2 \log_2 n_0$, quindi $$f^\ast(n,n_0) = \log_2\log_2 n - \log_2\log_2 n_0 - 1, \qquad f^\ast(n, 2) = \log_2\log_2 n - 1.$$ Più in generale, per $n = a^{b^k}$ e $f(n) = n^{1/b}$: $f^\ast(n, a) = \log_b\log_a n - 1$.
• $f(n) = n - 1$: $n - k > n_0 \iff k < n - n_0$, quindi $f^\ast(n, n_0) = n - n_0 - 1$ e $f^\ast(n, 1) = n - 2$.

Analisi dell'albero della ricorrenza

Studio di $(\ast)$. Per quanto visto, a livello $\ell$ le istanze hanno taglia $f^{(\ell)}(n)$ e l'ultimo livello non di base è $f^\ast(n,n_0)$. Per $0 \le \ell \le f^\ast(n, n_0)$ il lavoro di ogni nodo del livello $\ell$ è $w\bigl(f^{(\ell)}(n)\bigr)$; al livello $f^\ast(n,n_0) + 1$ il lavoro di ogni foglia è $T_0$.

Numero di nodi per livello. Al livello $0$ c'è un nodo, padre di $s(n)$ nodi del livello $1$; ognuno di questi genera $s(f(n))$ nodi del livello $2$, e così via: un nodo del livello $\ell$ genera $s\bigl(f^{(\ell)}(n)\bigr)$ figli. Quindi i nodi del livello $\ell$ sono $$s(n)\cdot s\bigl(f(n)\bigr)\cdots s\bigl(f^{(\ell-1)}(n)\bigr) = \prod_{j=0}^{\ell-1} s\bigl(f^{(j)}(n)\bigr),$$ per $0 \le \ell \le f^\ast(n,n_0) + 1$. Si usano le convenzioni dell'elemento neutro: somma vuota $\sum_{i=a}^{b} \dots = 0$ e prodotto vuoto $\prod_{i=a}^{b} \dots = 1$ per $a > b$; così il livello $0$ ha $1$ nodo, e $n \le n_0$ (con $f^\ast = -1$) dà $T(n) = T_0$.

LIVELLO            TAGLIA       NODI/LIVELLO                    LAVORO/NODO
0                  f^(0)(n)     1                               w(f^(0)(n))
1                  f^(1)(n)     s(f^(0)(n))                     w(f^(1)(n))
...
l  (0<=l<=f*)      f^(l)(n)     prod_{j=0}^{l-1} s(f^(j)(n))    w(f^(l)(n))
...
f*+1  (foglie)     <= n0        prod_{j=0}^{f*} s(f^(j)(n))     T0

Per ottenere $T(n)$ si sommano, riga per riga, i prodotti delle ultime due colonne (il lavoro cumulativo del livello):

Formula generale. $$T(n) = \sum_{\ell=0}^{f^\ast(n,n_0)} \left[\prod_{j=0}^{\ell-1} s\bigl(f^{(j)}(n)\bigr)\right] w\bigl(f^{(\ell)}(n)\bigr) \;+\; \left[\prod_{j=0}^{f^\ast(n,n_0)} s\bigl(f^{(j)}(n)\bigr)\right] T_0.$$

La correttezza dipende anche dalle convenzioni sopra. Dimostrazione per induzione, che nelle dispense è lasciata come esercizio:

Dimostrazione (induzione su $n$).

• [B] Se $n \le n_0$, $f^\ast = -1$: la somma è vuota ($0$) e il prodotto vuoto ($1$), quindi $T(n) = T_0$.
• [HP] La formula vale per ogni taglia $m < n$, con $n > n_0$.
• [TH] $T(n) = s(n)\,T(f(n)) + w(n)$ e $f(n) < n$, quindi per [HP] si applica a $f(n)$. Valgono $f^{(j)}(f(n)) = f^{(j+1)}(n)$ e $f^\ast(f(n), n_0) = f^\ast(n,n_0) - 1$ (se $f(n) \le n_0$ allora $f^\ast(n,n_0) = 0$ e $f^\ast(f(n),n_0) = -1$ per convenzione). Posto $F = f^\ast(n,n_0)$: $$T(f(n)) = \sum_{\ell=0}^{F-1} \left[\prod_{j=0}^{\ell-1} s\bigl(f^{(j+1)}(n)\bigr)\right] w\bigl(f^{(\ell+1)}(n)\bigr) + \left[\prod_{j=0}^{F-1} s\bigl(f^{(j+1)}(n)\bigr)\right] T_0.$$ Moltiplicando per $s(n)$, che è il fattore $j = 0$ di ogni prodotto, e cambiando indici $\ell' = \ell + 1$, $j' = j + 1$: $$s(n)\,T(f(n)) = \sum_{\ell'=1}^{F} \left[\prod_{j'=0}^{\ell'-1} s\bigl(f^{(j')}(n)\bigr)\right] w\bigl(f^{(\ell')}(n)\bigr) + \left[\prod_{j'=0}^{F} s\bigl(f^{(j')}(n)\bigr)\right] T_0.$$ Aggiungendo $w(n) = \bigl[\prod_{j=0}^{-1}\bigr] w(f^{(0)}(n))$, cioè il termine $\ell = 0$, si ottiene la formula per $T(n)$. $\square$

Esempi di applicazione

Esempio 1: $s = 6$, $f = n/3$

$$T(n) = \begin{cases} 4 & n = 1 \\ 6\,T(n/3) + n(n-1) & n > 1, \end{cases} \qquad n = 3^k.$$ Parametri: $s(n) = 6$, $f(n) = n/3$, $w(n) = n^2 - n$, $T_0 = 4$, $n_0 = 1$; quindi $f^{(\ell)}(n) = n/3^\ell$, $f^\ast(n,1) = \log_3 n - 1$, $\prod_{j<\ell} 6 = 6^\ell$ e $w(f^{(\ell)}(n)) = \frac{n^2}{9^\ell} - \frac{n}{3^\ell}$. La formula dà $$T(n) = \underbrace{\sum_{\ell=0}^{\log_3 n - 1} 6^\ell \left(\frac{n^2}{9^\ell} - \frac{n}{3^\ell}\right)}_{A} + \underbrace{6^{\log_3 n}\cdot 4}_{B}.$$ Parte $B$. Con l'identità $a^{\log_c b} = b^{\log_c a}$ si ha $6^{\log_3 n} = n^{\log_3 6} = n^{\log_3 2 + \log_3 3} = n^{1 + \log_3 2}$, quindi $B = 4\,n^{1+\log_3 2}$. Queste riscritture servono a portare i termini in forma standard per poi semplificare.

Parte $A$. Spezzando la somma e usando $6^\ell/9^\ell = (2/3)^\ell$ e $6^\ell/3^\ell = 2^\ell$: $$\begin{aligned} A &= n^2 \sum_{\ell=0}^{\log_3 n - 1} \left(\tfrac23\right)^\ell - n \sum_{\ell=0}^{\log_3 n - 1} 2^\ell = n^2 \cdot \frac{1 - (2/3)^{\log_3 n}}{1 - 2/3} - n\cdot\frac{1 - 2^{\log_3 n}}{1 - 2}. \end{aligned}$$ Con $(2/3)^{\log_3 n} = n^{\log_3(2/3)} = n^{\log_3 2 - 1}$ e $2^{\log_3 n} = n^{\log_3 2}$: $$A = 3n^2\bigl(1 - n^{\log_3 2 - 1}\bigr) + n\bigl(1 - n^{\log_3 2}\bigr) = 3n^2 - 3n^{1 + \log_3 2} + n - n^{1+\log_3 2} = 3n^2 - 4n^{1+\log_3 2} + n.$$ Somma. $T(n) = A + B = 3n^2 - 4n^{1+\log_3 2} + n + 4n^{1+\log_3 2} = \mathbf{3n^2 + n}$.

Verifica per induzione (logicamente non necessaria, perché la formula è dimostrata, ma utile contro gli errori di calcolo): base $T(1) = 4 = 3 + 1$; passo, per $n > 1$: $T(n) = 6\,T(n/3) + n(n-1) = 6\left(3\frac{n^2}{9} + \frac n3\right) + n^2 - n = 2n^2 + 2n + n^2 - n = 3n^2 + n$.

Esempio 2: $s = 2$, $f = \sqrt n$

$$T(n) = \begin{cases} 1 & n = 2 \\ 2\,T(\sqrt n) + 1 & n > 2, \end{cases} \qquad n = 2^{2^k}.$$ Parametri: $s = 2$, $f(n) = \sqrt n$, $w = 1$, $n_0 = 2$, $T_0 = 1$; $f^{(\ell)}(n) = n^{1/2^\ell}$, $f^\ast(n,2) = \log_2\log_2 n - 1$, $\prod_{j<\ell} 2 = 2^\ell$: $$T(n) = \sum_{\ell=0}^{\log_2\log_2 n - 1} 2^\ell \cdot 1 + 2^{\log_2\log_2 n}\cdot 1 = \bigl(2^{\log_2\log_2 n} - 1\bigr) + 2^{\log_2\log_2 n} = 2\log_2 n - 1,$$ perché $2^{\log_2\log_2 n} = \log_2 n$. Controllo: $T(2) = 1$, $T(4) = 2T(2) + 1 = 3 = 2\cdot 2 - 1$, $T(16) = 7$, $T(256) = 15$.

Esempio 3: merge sort, conteggio esatto

$s = 2$, $f = n/2$, $w = n - 1$, $T_0 = 0$, $n_0 = 1$, $n = 2^k$: $f^\ast = \log_2 n - 1$, nodi al livello $\ell$: $2^\ell$, lavoro per nodo $\frac{n}{2^\ell} - 1$. Ogni livello costa $2^\ell\left(\frac{n}{2^\ell} - 1\right) = n - 2^\ell$: $$T(n) = \sum_{\ell=0}^{\log_2 n - 1}\left(n - 2^\ell\right) + 0 = n\log_2 n - (n - 1) = n\log_2 n - n + 1.$$ Per $n = 8$: $24 - 8 + 1 = 17$ (verificato con il conteggio della ricorrenza).

Esempio 4: la contrazione $f(n) = n - 1$

$T(n) = 2\,T(n-1) + 1$ con $T(1) = 1$ (le torri di Hanoi): $s = 2$, $f = n - 1$, $w = 1$, $n_0 = 1$, $T_0 = 1$, $f^\ast(n,1) = n - 2$, nodi al livello $\ell$: $2^\ell$: $$T(n) = \sum_{\ell=0}^{n-2} 2^\ell + 2^{n-1}\cdot 1 = (2^{n-1} - 1) + 2^{n-1} = 2^n - 1.$$ Con $f(n) = n - 1$ l'albero è molto profondo ($n - 1$ livelli) e con $s = 2$ le foglie sono $2^{n-1}$: esponenziale. Con $s = 1$, per esempio $T(n) = T(n-1) + n$ con $T(1) = 1$, i livelli costano $n - \ell$ e la formula dà $\sum_{\ell=0}^{n-2}(n - \ell) + 1 = \frac{n(n+1)}{2}$.

Taglia delle foglie diversa da $1$ (algoritmi ibridi)

Se la ricorsione si ferma a $n_0 > 1$ (per esempio si passa a un algoritmo diverso sotto una soglia), con $f(n) = n/b$ e $n/n_0$ potenza di $b$, si ha $f^\ast = \log_b(n/n_0) - 1$ e le foglie sono $a^{\log_b(n/n_0)} = (n/n_0)^{\log_b a}$ con lavoro $T_0$, che può dipendere da $n_0$. Esempio con $a = 2$, $b = 2$, $w(n) = n$, $n_0 = 4$, $T_0 = 5$: $$T(n) = \sum_{\ell=0}^{\log_2 n - 3} 2^\ell\frac{n}{2^\ell} + \frac n4\cdot 5 = n(\log_2 n - 2) + \frac{5n}{4},$$ per esempio $T(8) = 8 + 10 = 18$. È la situazione degli esercizi con algoritmo ibrido: Esercizio - algoritmo ibrido e valore ottimo della soglia (compito del 27 gennaio 2025, es. 1) e Esercizio - algoritmo ibrido con soglia ottima e confronto con la versione ricorsiva (compito del 4 settembre 2024, es. 1).

Verifica automatica

import math
from functools import lru_cache

def T_rec(n, n0, T0, s, f, w):           # ricorrenza (*) applicata alla lettera
    return T0 if n <= n0 else s(n) * T_rec(f(n), n0, T0, s, f, w) + w(n)

def T_formula(n, n0, T0, s, f, w):       # formula generale per livelli
    if n <= n0:
        return T0
    taglie = [n]
    while f(taglie[-1]) > n0:
        taglie.append(f(taglie[-1]))
    F = len(taglie) - 1                  # = f*(n, n0)
    tot, prod = 0, 1
    for l in range(F + 1):
        tot += prod * w(taglie[l])
        prod *= s(taglie[l])
    return tot + prod * T0

# esempio 1: 6T(n/3) + n(n-1), T(1) = 4
for k in range(12):
    n = 3**k
    assert T_rec(n, 1, 4, lambda m: 6, lambda m: m // 3, lambda m: m*m - m) \
        == T_formula(n, 1, 4, lambda m: 6, lambda m: m // 3, lambda m: m*m - m) == 3*n*n + n

La formula coincide con la ricorrenza anche per funzioni $s$, $f$, $w$ qualsiasi non decrescenti (controllato su 500 casi con $f(n) = \lfloor n/b\rfloor$, $s$ costante o dipendente da $n$, $f(n) = \lfloor\sqrt n\rfloor$).

Errori comuni

• Dimenticare di portare i termini in forma standard (potenze di $n$ con esponente $\log$) prima di sommare: i termini che si cancellano ($-4n^{1+\log_3 2}$ e $+4n^{1+\log_3 2}$) non si riconoscono.
• Contare i livelli sbagliati: i livelli non di base sono $0..f^\ast$ (cioè $f^\ast + 1$ livelli) e le foglie stanno al livello $f^\ast + 1$, con costo $T_0$ per foglia e non $w$.
• Usare $s(n)$ invece di $s(f^{(j)}(n))$ nel prodotto quando $s$ dipende dalla taglia.
• Dimenticare la somma dei costi delle foglie $\bigl[\prod s\bigr] T_0$ (se $T_0 > 0$ domina nei casi con molte foglie).
• Usare la formula con $n$ non della forma richiesta ($n = b^k$, o $n = a^{b^k}$) senza dirlo: i risultati valgono per quei $n$.

Domande d'esame

1. Risolvere con la formula generale $T(n) = 4T(n/2) + n$, $T(1) = 1$, per $n = 2^k$. Traccia: $s = 4$, $f = n/2$, $w = n$, $T_0 = 1$, $f^\ast = \log_2 n - 1$; il livello $\ell$ costa $4^\ell \cdot \frac{n}{2^\ell} = n\,2^\ell$, quindi $T(n) = n(n-1) + 4^{\log_2 n} = n^2 - n + n^2 = 2n^2 - n$.
2. Che cosa rappresenta $f^\ast(n, n_0)$ e quanto vale per $f(n) = n/2$, $n_0 = 1$? Risposta: l'ultimo livello dell'albero con istanze non di base; $\log_2 n - 1$; le foglie sono al livello $\log_2 n$.
3. Qual è la complessità esatta (in confronti) del merge sort nel caso peggiore per $n = 2^k$? $n\log_2 n - n + 1$.