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
con
e
, in alcuni casi si può ottenere una soluzione confrontando
con la funzione
. Se
è asintoticamente polinomialmente più piccola (ovvero più piccola per almeno un fattore polinomiale
allora
; se le due funzioni hanno asintoticamente la stessa grandezza allora
; infine, se
è sufficientemente regolare e polinomialmente più grande allora
. Non sono coperti dal teorema i casi in cui
sia asintoticamente più grande o più piccola di
in modo non polinomiale.[3]
Sia data una relazione di ricorrenza
nella forma[4]
![{\displaystyle T(n)=aT\left({\frac {n}{b}}\right)+f(n),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/657aa2f3370db87532b4ee43be214ee765583c9d)
dove
e
sono costanti e
si può interpretare sia come
(parte intera)
sia come
(parte intera superiore).
Allora la funzione
è limitata asintoticamente secondo uno dei tre seguenti casi:
- se esiste una costante
tale che
, allora
;
- se
, allora
;
- se esiste una costante
tale che
ed esistono una costante
e un intero
tali che
, allora
.[5]
La somma
definita su potenze di
, dove
e
sono costanti e
è non negativa, ha rispettivamente comportamento asintotico:
- sotto l'ipotesi del caso 1 del teorema principale,
;
- sotto l'ipotesi del caso 2 del teorema principale,
;
- sotto l'ipotesi del caso 3 del teorema principale, se esistono una costante
e un intero
tali che
, allora
.
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/661b7488afa25c0e52ecce069245d51cbe26feaa)
che sostituita in
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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63f343e9aae7638cda130386746745b9f601754a)
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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81836d4df8eaac9501a4b7364a52d75a7fc18396)
Poiché
e
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),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5187322aa2aee9d4bb1cfe17ddc5fbeed596e868)
e dal fatto che, poiché
è 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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef5d66c570d73a1ed6c8deae4adab40c303483bf)
che insieme danno
![{\displaystyle s(n)\in \Theta (n^{\log _{b}a})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/640f7eec97f27c8955ab8d023db06c5766b1a5c0)
da cui la tesi.
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/684fa844427ff66c2b2163016dd38d2c93f64983)
che sostituita in
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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4b52f3d5bd5c551e69d7b011b9cd6da06304735)
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f337111e01c92056e84d8c223b2b8588b0c1d12)
da cui la tesi.
Applicando iterativamente
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fb36cf7273795de7bc63d97171d3ecb7f32a607)
per valori sufficientemente grandi di
. Tale condizione vale dunque per tutti tranne al più un numero costante di termini, per i quali
non è sufficientemente grande. Analogamente ai casi precedenti, si sostituisce nella definizione di
, 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),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3adf927142046b04a1cc451f79366280711e30b)
dove
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a48ff4ecf873fb08b2d6eee168d97e65929e7bda)
e poiché la definizione di
contiene
in una somma a termini non negativi, si ha anche
. Combinando le due limitazioni asintotiche, si ha
.[6]
Nel caso particolare in cui
sia definita solo su potenze esatte di
, 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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be1164488f1a79044b39185a84cb383027e2c01c)
Applicando quindi il lemma dimostrato precedentemente, si ottiene immediatamente la validità del teorema principale nel caso particolare in cui
sia definita su potenze di
. 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
-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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad73f3ff492548129957ae71e714bc0aefd73ff4)
Poiché dalla definizione di parte intera superiore si ha
, 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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a334c56e174ff8b9c8ba35bb3ecb7a856f8a7c4)
Da ciò si osserva che
, quindi alla profondità di ricorsione
il costo del problema è limitato da una costante. Si generalizza quindi la prima equazione per
arbitrario, non più ristretto alle potenze di
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12009da83c0cc44bfb44bfd619224d1f53c9eaf8)
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
si ha che esiste una costante
e un intero
tali che, per
![{\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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4111e33d4f96234ae7e1d5b09252c6b92b5cc5d0)
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/657da74e50d4a47849426506c2f9e6f7e0778477)
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]
Il secondo caso del teorema principale può essere generalizzato sostituendo solo alla sua ipotesi particolare,
per qualche
e alla tesi
.[9] Come si vede il caso non generale è per
.
Il teorema di Akra-Bazzi generalizza il teorema principale, sotto opportune ipotesi, per relazioni di ricorrenza nella forma
.
Sia data la seguente relazione di ricorrenza:
![{\displaystyle T_{A}(n)=9\,T_{A}\left({\frac {n}{3}}\right)+n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6828cbaf5583813435f0c44eeea84e69dfbcc49)
Si ha
,
e
. Allora
Dato che
quando
, è possibile applicare il caso 1 del teorema dell'esperto ottenendo la soluzione
![{\displaystyle T_{A}(n)=\Theta \left(n^{2}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/473ed9e08a569a64833d8268744331d25cae8b6d)
Sia data ora la relazione di ricorrenza:
![{\displaystyle T_{A}(n)=T_{A}\left({\frac {2\,n}{3}}\right)+1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/482586162376e81e2e045482c4ae3fc3406fe4df)
in cui
,
e
. Essendo
ed
, vale il caso 2 del teorema dell'esperto, che porta alla soluzione
Infine sia data la relazione di ricorrenza:
![{\displaystyle T_{A}(n)=3\,T_{A}\left({\frac {n}{4}}\right)+n\log n,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de179f71c066b6cdc41ce6324726c502afface13)
in cui
,
e
. Essendo
ed
, in cui
, il caso 3 del teorema dell'esperto si può applicare solo se vale la condizione di regolarità per
. Per
sufficientemente grande si ha
per
. Di conseguenza la soluzione della ricorrenza è
- ^ Questo il significato originario del termine master nel nome.
- ^ Jon Louis Bentley, Dorothea Haken e James B. Saxe, A general method for solving divide-and-conquer recurrences, in ACM SIGACT News, vol. 12, n. 3, September 1980, pp. 36–44, DOI:10.1145/1008861.1008865.
- ^ Cormen et al., pp. 94–95.
- ^ Considerando un algoritmo ricorsivo associato alla relazione di ricorrenza, le quantità coinvolte si possono interpretare come:
è la dimensione dell'input;
è il numero di chiamate ricorsive all'algoritmo;
è la dimensione della chiamata ricorsiva (ovvero la porzione del problema originale rappresentato in ogni sottoproblema);
è la funzione di costo della fase di suddivisione del problema e di ricostruzione della soluzione.
- ^ Cormen et al., p. 94.
- ^ Cormen et al., pp. 100–102.
- ^ Cormen et al., pp. 98–100.
- ^ Cormen et al., pp. 103–106.
- ^ Goodrich & Tamassia, pp. 268–270.
- 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.