Algoritmi di elevamento a potenza
# Algoritmi di elevamento a potenza

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:

${\begin{matrix}a^{n}:=&\underbrace {a\cdot a\cdot a\cdots a} \\&n{\mbox{ volte}}\end{matrix}}$

Di seguito la versione iterativa dell'algoritmo:

Tale algoritmo ha complessità $O(n)$, poiché vengono effettuate $n$ moltiplicazioni.

### Algoritmo ottimo

Vediamo ora un algoritmo più efficiente:

L'equazione di ricorrenza è la seguente: $T(n)={\begin{cases}{\Theta }(1),&{\mbox{se }}n{\mbox{ ≤ 1}}\\T(n/2)+{\Theta }(1),&{\mbox{se }}n>1\end{cases}}$.

Poiché essa è del tipo $T(n)=aT\left({\frac {n}{b}}\right)+f(n)$, può essere risolta utilizzando il metodo dell'esperto.

Il costo in tempo di questo algoritmo è $O(\log n)$, quindi asintoticamente migliore rispetto al precedente.

