Scrivere un algoritmo \( \operatorname{FastPower}(a,n) \) che prende come input un numero \(a\) e un intero non negativo \(n \) e ritorna \(a^n \) ma la complessità computazionale dev'essere \( \Theta(\log n) \).
Ora io ho fatto così
- Codice:
if n == 0
return 1
ans = FastPower(a, floor(n/2))
if n is even
return ans * ans
else
return ans* ans * a
Se diciamo che \( T(n) \) è il tempo richiesto per eseguire \( \operatorname{FastPower}(a,n) \) allora chiaramente \( T(n) = T(n/2) + \Theta(1) \) dove \( T(0) = \Theta(1) \) quindi per il teorema principale abbiamo che \( T(n) = \Theta( \log n ) \). E le soluzioni dicono esattamente questo.
Il punto è che mi è sorto un dilemma, evidentemente qui la complessità nel fare la moltiplicazione ans * ans oppure ans* ans * a è costante, ma allora perché se moltiplico due numeri interi di \(n \) cifre, ottengo una complessità di \( \Theta(n^2) \) o se fatto in modo furbo \( \Theta(n \log n) \), ma comunque non lineare. Com'è possibile questa distinzione ? Sarà una domanda banale, ma non sono un informatico e quindi magari mi sfugge qualcosa di come il computer interpreta una moltiplicazione tipo ans*ans dall'avere un risultato esatto tra due numeri interi.