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^[1] per una famiglia di ricorrenze.^[2] 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 ${\displaystyle T(n)=aT\left({\frac {n}{b}}\right)+f(n)}$ con ${\displaystyle a\geq 1}$ e ${\displaystyle b>1}$, in alcuni casi si può ottenere una soluzione confrontando ${\displaystyle f}$ con la funzione ${\displaystyle n^{\log _{b}a}}$. Se ${\displaystyle f}$ è asintoticamente polinomialmente più piccola (ovvero più piccola per almeno un fattore polinomiale ${\displaystyle n^{\varepsilon }}$ allora ${\displaystyle T(n)=\Theta (n^{\log _{b}a})}$; se le due funzioni hanno asintoticamente la stessa grandezza allora ${\displaystyle T(n)=\Theta (n^{\log _{b}a}\log(n))=\Theta \left(f(n)\log(n)\right)}$; infine, se ${\displaystyle f}$ è sufficientemente regolare e polinomialmente più grande allora ${\displaystyle T(n)=\Theta \left(f(n)\right)}$. Non sono coperti dal teorema i casi in cui ${\displaystyle f}$ sia asintoticamente più grande o più piccola di ${\displaystyle n^{\log _{b}a}}$ in modo non polinomiale.^[3]

Enunciato

Sia data una relazione di ricorrenza ${\displaystyle T(n)}$ nella forma^[4]

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

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

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

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

Dimostrazione

Lemma

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

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

Dimostrazione

Caso 1

Per il caso 1, l'ipotesi implica

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

che sostituita in ${\displaystyle s}$ porta a

${\displaystyle 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

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

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

${\displaystyle 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é ${\displaystyle f(1)}$ è una costante,

${\displaystyle 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

${\displaystyle 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

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

che sostituita in ${\displaystyle s}$ porta a

${\displaystyle 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

${\displaystyle 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 ${\displaystyle i}$ volte l'ipotesi di regolarità del caso 3, si ha

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

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

${\displaystyle 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 ${\displaystyle O(1)}$ rappresenta i termini precedentemente citati per i quali non vale la disuguaglianza. Sommando la serie geometrica si ha

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

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

Dimostrazione del teorema principale

Nel caso particolare in cui ${\displaystyle T}$ sia definita solo su potenze esatte di ${\displaystyle b}$, analizzando l'albero della ricorsione relativo alla relazione di ricorrenza si osserva che^[7]

${\displaystyle 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 ${\displaystyle n}$ sia definita su potenze di ${\displaystyle 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 ${\displaystyle i}$-esima l'argomento assume la forma

${\displaystyle 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 ${\displaystyle \lceil x\rceil \leq x+1}$, si ottiene

${\displaystyle 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 ${\displaystyle n_{\lfloor \log _{b}n\rfloor }=O(1)}$, quindi alla profondità di ricorsione ${\displaystyle \lfloor \log _{b}n\rfloor }$ il costo del problema è limitato da una costante. Si generalizza quindi la prima equazione per ${\displaystyle n}$ arbitrario, non più ristretto alle potenze di ${\displaystyle b}$

${\displaystyle 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 ${\displaystyle n_{i}}$ si ha che esiste una costante ${\displaystyle c>0}$ e un intero ${\displaystyle n_{0}}$ tali che, per ${\displaystyle n\geq n_{0}}$

${\displaystyle 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

${\displaystyle 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.^[8]

Generalizzazioni

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

Il teorema di Akra-Bazzi generalizza il teorema principale, sotto opportune ipotesi, per relazioni di ricorrenza nella forma ${\displaystyle 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:

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

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

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

Caso 2

Sia data ora la relazione di ricorrenza:

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

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

Caso 3

Infine sia data la relazione di ricorrenza:

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

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