In informatica, per algoritmi di elevamento a potenza si intende la serie di passaggi elementari che una generica CPU deve compiere per eseguire l'operazione di elevamento a potenza.
Pseudo-codice e complessità Algoritmo banale L'algoritmo di elevamento a potenza più semplice si basa sulla definizione matematica dell'operazione di potenza:
Di seguito la versione iterativa dell'algoritmo:
function POWER(base, exponent) result = 1; for i = 1 to exponent result = result * base;
Tale algoritmo ha complessità , poiché vengono effettuate moltiplicazioni. Algoritmo ottimo Vediamo ora un algoritmo più efficiente:
function POWER(base, exponent) if exponent == 0 return 1; if exponent == 1 return base; if (exponent % 2) == 0 return POWER(base * base, exponent/2); else return base * POWER(base * base, exponent/2); return 0;
L'equazione di ricorrenza è la seguente: .
Poiché essa è del tipo , può essere risolta utilizzando il metodo dell'esperto.
Il costo in tempo di questo algoritmo è , quindi asintoticamente migliore rispetto al precedente.
Bibliografia
Voci correlate Algoritmi di moltiplicazione Algoritmi di ordinamento Ricerca dicotomica
Elevamento a potenza