Teorema dell'esperto

Il teorema dell'esperto, noto anche come teorema principale (in inglese master theorem) o teorema del maestro, è un teorema inerente all'analisi degli algoritmi che fornisce una soluzione asintotica ad una famiglia di relazioni di ricorrenza. È stato inizialmente esposto da Jon Bentley, Dorothea Haken, e James B. Saxe nel 1980, dove fu descritto come un metodo unificato per una famiglia di ricorrenze. Il nome di questo teorema è stato popolarizzato dal famoso manuale Introduzione agli algoritmi di Cormen, Leiserson, Rivest e Stein. Non fornisce una soluzione a tutte le possibili relazioni di ricorrenza, ed una sua generalizzazione è il teorema di Akra-Bazzi.

Informalmente, il teorema afferma che, data una relazione di ricorrenza nella forma $T(n)=aT\left({\frac {n}{b}}\right)+f(n)$ con $a\geq 1$ e $b>1$, in alcuni casi si può ottenere una soluzione confrontando $f$ con la funzione $n^{\log _{b}a}$. Se $f$ è asintoticamente polinomialmente più piccola (ovvero più piccola per almeno un fattore polinomiale $n^{\varepsilon }$ allora $T(n)=\Theta (n^{\log _{b}a})$; se le due funzioni hanno asintoticamente la stessa grandezza allora $T(n)=\Theta (n^{\log _{b}a}\log(n))=\Theta \left(f(n)\log(n)\right)$; infine, se $f$ è sufficientemente regolare e polinomialmente più grande allora $T(n)=\Theta \left(f(n)\right)$. Non sono coperti dal teorema i casi in cui $f$ sia asintoticamente più grande o più piccola di $n^{\log _{b}a}$ in modo non polinomiale.

Enunciato

Sia data una relazione di ricorrenza $T(n)$ nella forma

$T(n)=aT\left({\frac {n}{b}}\right)+f(n),$

dove $a\geq 1$ e $b>1$ sono costanti e ${\frac {n}{b}}$ si può interpretare sia come $\left\lfloor {\frac {n}{b}}\right\rfloor$ (parte intera) sia come $\left\lceil {\frac {n}{b}}\right\rceil$ (parte intera superiore).

Allora la funzione $\,T(n)$ è limitata asintoticamente secondo uno dei tre seguenti casi:

1. se esiste una costante $\varepsilon >0$ tale che $f(n)=O\left(n^{\log _{b}a-\varepsilon }\right)$, allora $T(n)=\Theta \left(n^{\log _{b}a}\right)$;
2. se $f(n)=\Theta \left(n^{\log _{b}a}\right)$, allora $T(n)=\Theta \left(n^{\log _{b}a}\log n\right)$;
3. se esiste una costante $\varepsilon >0$ tale che $f(n)=\Omega \left(n^{\log _{b}a+\varepsilon }\right)$ ed esistono una costante $0<c<1$ e un intero $n_{0}$ tali che $\forall n\geq n_{0}\colon af\left({\frac {n}{b}}\right)\leq cf(n)$, allora $T(n)=\Theta (f(n))$.

Dimostrazione

Lemma

La somma $s(n)=\sum _{i=0}^{\log _{b}n}a^{i}f\left({\frac {n}{b^{i}}}\right)$ definita su potenze di $b$, dove $a\geq 1$ e $b>1$ sono costanti e $f$ è non negativa, ha rispettivamente comportamento asintotico:

1. sotto l'ipotesi del caso 1 del teorema principale, $s(n)=\Theta \left(n^{\log _{b}a}\right)$;
2. sotto l'ipotesi del caso 2 del teorema principale, $s(n)=\Theta \left(n^{\log _{b}a}\log n\right)$;
3. sotto l'ipotesi del caso 3 del teorema principale, se esistono una costante $0<c<1$ e un intero $n_{0}$ tali che $\forall n\geq n_{0}\colon af\left({\frac {n}{b}}\right)\leq cf(n)$, allora $s(n)=\Theta \left(f(n)\right)$.

Dimostrazione

Caso 1

Per il caso 1, l'ipotesi implica

$f\left({\frac {n}{b^{j}}}\right)=O\left(\left({\frac {n}{b^{j}}}\right)^{\log _{b}a-\varepsilon }\right)$

che sostituita in $s$ porta a

$s(n)=O\left(\sum _{i=0}^{\log _{b}n-1}a^{i}\left({\frac {n}{b^{i}}}\right)^{\log _{b}a-\varepsilon }\right).$

Raccogliendo i fattori comuni, semplificando e sommando la serie geometrica troncata risultante, si ha

$s(n)=O\left(n^{\log _{b}a-\varepsilon }\left({\frac {n^{\varepsilon }-1}{b^{\varepsilon }-1}}\right)\right).$

Poiché $\varepsilon$ e $b$ sono costanti, si ha

$n^{\log _{b}a-\varepsilon }\left({\frac {n^{\varepsilon }-1}{b^{\varepsilon }-1}}\right)=n^{\log _{b}a-\varepsilon }O\left(n^{\varepsilon }\right)=O\left(n^{\log _{b}a}\right),$

e dal fatto che, poiché $f(1)$ è una costante,

$s(n)\geq a^{\log _{b}n}f(1)=f(1)n^{\log _{b}a}\to s(n)\in \Omega (n^{\log _{b}a})$

che insieme danno

$s(n)\in \Theta (n^{\log _{b}a})$

da cui la tesi.

Caso 2

Analogamente al caso 1, per il caso 2 l'ipotesi implica

$f\left({\frac {n}{b^{j}}}\right)=\Theta \left(\left({\frac {n}{b^{j}}}\right)^{\log _{b}a}\right)$

che sostituita in $s$ porta a

$s(n)=\Theta \left(\sum _{i=0}^{\log _{b}n-1}a^{i}\left({\frac {n}{b^{i}}}\right)^{\log _{b}a}\right).$

Si procede analogamente al caso precedente, tuttavia la serie troncata ottenuta non è una serie geometrica, ma una serie a termini costanti

$n^{log_{b}a}\sum _{i=0}^{\log _{b}n-1}1=n^{\log _{b}a}\log _{b}n$

da cui la tesi.

Caso 3

Applicando iterativamente $i$ volte l'ipotesi di regolarità del caso 3, si ha

$a^{i}f\left({\frac {n}{b^{i}}}\right)\leq c^{i}f(n)$

per valori sufficientemente grandi di $n$. Tale condizione vale dunque per tutti tranne al più un numero costante di termini, per i quali $n$ non è sufficientemente grande. Analogamente ai casi precedenti, si sostituisce nella definizione di $s$, ottenendo

$s(n)\leq \sum _{i=0}^{\log _{b}n}c^{i}f(n)+O(1)\leq f(n)\sum _{i=0}^{\infty }c^{i}+O(1),$

dove $O(1)$ rappresenta i termini precedentemente citati per i quali non vale la disuguaglianza. Sommando la serie geometrica si ha

$s(n)=f(n)\left({\frac {1}{1-c}}\right)+O(1)=O\left(f(n)\right)$

e poiché la definizione di $s$ contiene $f$ in una somma a termini non negativi, si ha anche $s(n)=\Omega \left(f(n)\right)$. Combinando le due limitazioni asintotiche, si ha $s(n)=\Theta \left(f(n)\right)$.

Dimostrazione del teorema principale

Nel caso particolare in cui $T$ sia definita solo su potenze esatte di $b$, analizzando l'albero della ricorsione relativo alla relazione di ricorrenza si osserva che

$T(n)=\sum _{i=0}^{\log _{b}n}a^{i}f\left({\frac {n}{b^{i}}}\right)+\Theta \left(n^{\log _{b}a}\right).$

Applicando quindi il lemma dimostrato precedentemente, si ottiene immediatamente la validità del teorema principale nel caso particolare in cui $n$ sia definita su potenze di $b$. Questo ovviamente non è sufficiente a dimostrare il teorema, ma può essere esteso al caso generale considerando il caso in cui compaiano parti intere superiori o inferiori.

Nel caso di una parte intera superiore, nel considerare l'albero di ricorsione alla chiamata $i$-esima l'argomento assume la forma

$n_{i}={\begin{cases}n,\quad &i=0,\\\lceil {\frac {n_{i-1}}{b}}\rceil ,&i>0.\end{cases}}$

Poiché dalla definizione di parte intera superiore si ha $\lceil x\rceil \leq x+1$, si ottiene

$n_{i}\leq {\frac {n}{b^{i}}}+\sum _{i=0}^{i-1}{\frac {1}{b^{i}}}<{\frac {n}{b^{i}}}+{\frac {b}{b-1}}.$

Da ciò si osserva che $n_{\lfloor \log _{b}n\rfloor }=O(1)$, quindi alla profondità di ricorsione $\lfloor \log _{b}n\rfloor$ il costo del problema è limitato da una costante. Si generalizza quindi la prima equazione per $n$ arbitrario, non più ristretto alle potenze di $b$

$T(n)=\sum _{i=0}^{\lfloor \log _{b}n\rfloor }a^{i}f\left(n_{i}\right)+\Theta \left(n^{\log _{b}a}\right)$

e si può procedere a studiare la somma. Il terzo caso procede in maniera esattamente analoga al terzo caso del lemma. Per il secondo caso, dalla definizione di O-grande e ricordando l'espressione di $n_{i}$ si ha che esiste una costante $c>0$ e un intero $n_{0}$ tali che, per $n\geq n_{0}$

$f\left(n_{i}\right)\leq c\left({\frac {n}{b^{i}}}+{\frac {b}{b-1}}\right)^{\log _{b}a}\leq c\left({\frac {n^{\log _{b}a}}{a^{i}}}\right)\left(1+{\frac {b}{b-1}}\right)^{\log _{b}a}=O\left({\frac {n^{\log _{b}a}}{a^{i}}}\right).$

Il limite asintotico ottenuto permette di procedere poi in maniera analoga al caso 2 del lemma. Per il primo caso, in maniera analoga a quanto appena fatto si mostra che

$f\left(n_{i}\right)=O\left(\left({\frac {n}{b^{i}}}\right)^{\log _{b}a-\varepsilon }\right)$

che permette di procedere poi in maniera analoga al caso 1 del lemma. Questo completa la dimostrazione del teorema principale in caso di parte intera superiore, nel caso della parte intera inferiore la dimostrazione è analoga.

Generalizzazioni

Il secondo caso del teorema principale può essere generalizzato sostituendo solo alla sua ipotesi particolare, $f(n)=\Theta \left(n^{\log _{b}a}\log ^{k}n\right)$ per qualche $k\geq 0$ e alla tesi $T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)$. Come si vede il caso non generale è per $k=0$.

Il teorema di Akra-Bazzi generalizza il teorema principale, sotto opportune ipotesi, per relazioni di ricorrenza nella forma $T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x))$.

Esempi

Caso 1

Sia data la seguente relazione di ricorrenza:

$T_{A}(n)=9\,T_{A}\left({\frac {n}{3}}\right)+n.$

Si ha $a=9$, $b=3$ e $f(n)=n$. Allora $n^{\log _{b}a}=n^{\log _{3}9}=\Theta \left(n^{2}\right).$ Dato che $f(n)=O\left(n^{\log _{3}9-\varepsilon }\right)$ quando $\varepsilon =1$, è possibile applicare il caso 1 del teorema dell'esperto ottenendo la soluzione

$T_{A}(n)=\Theta \left(n^{2}\right).$

Caso 2

Sia data ora la relazione di ricorrenza:

$T_{A}(n)=T_{A}\left({\frac {2\,n}{3}}\right)+1,$

in cui $a=1$, $b=3/2$ e $f(n)=1$. Essendo $n^{\log _{b}a}=n^{\log _{3/2}1}=\Theta (n^{0})=\Theta (1)$ ed $f(n)=1$, vale il caso 2 del teorema dell'esperto, che porta alla soluzione $T_{A}(n)=\Theta (\log _{3}n).$

Caso 3

Infine sia data la relazione di ricorrenza:

$T_{A}(n)=3\,T_{A}\left({\frac {n}{4}}\right)+n\log n,$

in cui $a=3$, $b=4$ e $f(n)=n\log n$. Essendo $n^{\log _{b}a}=n^{\log _{4}3}=O\left(n^{0,793}\right)$ ed $f(n)=\Omega \left(n^{\log _{4}3+\varepsilon }\right)$, in cui $\varepsilon \approx 0,2$, il caso 3 del teorema dell'esperto si può applicare solo se vale la condizione di regolarità per $f(n)$. Per $n$ sufficientemente grande si ha $3\left({\frac {n}{4}}\right)\log \left({\frac {n}{4}}\right)\leq \left({\frac {3}{4}}n\log n\right)=cf(n)$ per $c=3/4\leq 1$. Di conseguenza la soluzione della ricorrenza è $T_{A}(n)=\Theta (n\log n).$

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduction to Algorithms, 3ª ed., MIT Press, 2009, pp. 93–106, ISBN 978-0-262-53305-8.
• Michael T. Goodrich e Roberto Tamassia, Algorithm Design: Foundation, Analysis, and Internet Examples, Wiley, 2002, ISBN 0-471-38365-1.

Voci correlate

• Algoritmo ricorsivo
• Relazione di ricorrenza
• Stima asintotica