Metodo di Akra-Bazzi

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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 i
  • per ogni i
  • per ogni i
  • , dove c è una costante e O è la notazione O grande
  • per ogni i
  • è una costante

Il comportamento asintotico di T(x) si trova determinando il valore di p per cui , sostituendolo poi nell'equazione

(vedi Θ). Intuitivamente rappresenta una pertubazione piccola nell'indice di T. notando che

e

sono sempre comprese tra 0 e 1, può essere utilizzato per escludere la parte intera nell'indice, e lo stesso di può fare per la parte intera superiore.

Quindi, e avranno, ai fini del metodo Akra-Bazzi, lo stesso comportamento asintotico.

Un esempio[modifica | modifica wikitesto]

Sia definita come

per gli
per

Applicando il metodo, il primo passo consiste nel trovare il valore di p per cui . Nell'esempio proposto, p = 2. Usando quindi la formula, sia ha per il comportamento asintotico

Impiego[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]