Teorema dell'esperto

Il teorema dell'esperto, noto anche come teorema principale (Template:Inglese) 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\ge 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^{\epsilon }$ allora $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$; se le due funzioni hanno asintoticamente la stessa grandezza allora $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log (n))=\mathrm{\Theta }(f(n)\log (n))$; infine, se $f$ è sufficientemente regolare e polinomialmente più grande allora $T(n)=\mathrm{\Theta }(f(n))$. 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\ge 1$ e $b>1$ sono costanti e $\frac{n}{b}$ si può interpretare sia come $\lfloor \frac{n}{b}\rfloor$ (parte intera) sia come $\lceil \frac{n}{b}\rceil$ (parte intera superiore).

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

1. se esiste una costante $\epsilon >0$ tale che $f(n)=O\left(n^{{\log }_{b}a-\epsilon }\right)$, allora $T(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$;
2. se $f(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$, allora $T(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}{\log }_{b}n\right)$;
3. se esiste una costante $\epsilon >0$ tale che $f(n)=\mathrm{\Omega }\left(n^{{\log }_{b}a+\epsilon }\right)$ ed esistono una costante $0<c<1$ e un intero $n_0$ tali che $\mathrm{\forall }n\ge n_0:af\left(\frac{n}{b}\right)\le cf(n)$, allora $T(n)=\mathrm{\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\ge 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)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$;
2. sotto l'ipotesi del caso 2 del teorema principale, $s(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log bn)$;
3. sotto l'ipotesi del caso 3 del teorema principale, se esistono una costante $0<c<1$ e un intero $n_0$ tali che $\mathrm{\forall }n\ge n_0:af\left(\frac{n}{b}\right)\le cf(n)$, allora $s(n)=\mathrm{\Theta }(f(n))$.

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-\epsilon }\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-\epsilon }\right).$

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

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

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

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

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

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

che insieme danno

$s(n)\in \mathrm{\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)=\mathrm{\Theta }\left({\left(\frac{n}{b^j}\right)}^{{\log }_{b}a}\right)$

che sostituita in $s$ porta a

$s(n)=\mathrm{\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^{lo{g}_{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)\le 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)\le \sum _{i=0}^{{\log }_{b}n}{c}^{i}f(n)+O(1)\le f(n)\sum _{i=0}^{\mathrm{\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(f(n))$

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

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)+\mathrm{\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{array}{cc}n,& i=0,\\ \lceil \frac{n_{i-1}}{b}\rceil ,& i>0.\end{array}$

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

$n_i\le \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)+\mathrm{\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\ge n_0$

$f\left(n_i\right)\le c{(\frac{n}{b^i}+\frac{b}{b-1})}^{{\log }_{b}a}\le c\left(\frac{n^{{\log }_{b}a}}{a^i}\right){(1+\frac{b}{b-1})}^{{\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-\epsilon }\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)=\mathrm{\Theta }\left(n^{{\log }_{b}a}{\log }^{k}n\right)$ per qualche $k\ge 0$ e alla tesi $T(n)=\mathrm{\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)=9T_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}=\mathrm{\Theta }\left(n^2\right).$ Dato che $f(n)=O\left(n^{{\log }_{3}9-\epsilon }\right)$ quando $\epsilon =1$, è possibile applicare il caso 1 del teorema dell'esperto ottenendo la soluzione

$T_A(n)=\mathrm{\Theta }\left(n^2\right).$

Caso 2

Sia data ora la relazione di ricorrenza:

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

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

Caso 3

Infine sia data la relazione di ricorrenza:

$T_A(n)=3T_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)=\mathrm{\Omega }\left(n^{{\log }_{4}3+\epsilon }\right)$, in cui $\epsilon \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)\le (\frac{3}{4}n\log n)=cf(n)$ per $c=3/4\le 1$. Di conseguenza la soluzione della ricorrenza è $T_A(n)=\mathrm{\Theta }(n\log n).$

Bibliografia

• Template:Cita libro
• Template:Cita libro

Voci correlate

• Algoritmo ricorsivo
• Relazione di ricorrenza
• Stima asintotica