In informatica, il metodo Akra-Bazzi, o teorema Akra-Bazzi, è utilizzato per analizzare il comportamento asintotico delle ricorrenze matematiche che appaiono nello studio degli algoritmi divide et impera, in cui i diversi sottoproblemi hanno dimensioni decisamente differenti. È una generalizzazione del teorema principale, in cui si assume che i sottoproblemi abbiano invece dimensioni simili.
La formula Il metodo Akra-Bazzi si applica alle formule ricorsive del tipo:
per
Le pre-condizioni sono:
vi sono sufficienti casi base; e sono costanti per ogni per ogni per ogni , dove è una costante e è la notazione O grande; per ogni è una costante.
Il comportamento asintotico di si trova determinando il valore di per cui , sostituendolo poi nell'equazione
(si veda Θ). Intuitivamente rappresenta una perturbazione piccola nell'indice di notando che
e
sono sempre comprese tra 0 e 1, può essere utilizzato per escludere la parte intera nell'indice, e lo stesso si può fare per la parte intera superiore.
Quindi, e avranno, ai fini del metodo Akra-Bazzi, lo stesso comportamento asintotico.
Un esempio Sia
Applicando il metodo, il primo passo consiste nel trovare il valore di per cui . Nell'esempio proposto, . Usando quindi la formula, si ha per il comportamento asintotico
Impiego Il metodo Akra-Bazzi è più utile di molte altre tecniche in quanto copre un ventaglio molto ampio di casi. La sua principale applicazione è l'approssimazione del tempo di esecuzione di molti algoritmi divide et impera. Ad esempio nel merge sort, il numero di comparazioni richieste nel caso peggiore, che è all'incirca proporzionale al tempo di esecuzione, è dato ricorsivamente da e
per gli , e può essere valutato come .
Bibliografia
Voci correlate Teorema principale Teoria della complessità algoritmica
Collegamenti esterni O Método de Akra-Bazzi na Resolução de Equações de Recorrência
Akra - Bazzi, teorema di Categoria:Teorie dell'informatica