Le potenze nello studio degli algoritmi

[absinth]

Ciao a tutti! Vi chiedo di aiutarmi con un dubbio: studiando una materia molto simile a "dati e algoritmi" (quella materia astratta dove si usano solo pseudocodici) mi sono accorto che nella soluzione di un esercizio invece di trascurare il calcolo della potenza ad esempio $a^k$ con un $a$ fissato, dice che sarebbe necessario un tempo $\log k$ per calcolarla.
Ad esempio scrivendo in java s = a^k; questa riga di codice ci metterebbe $\log k$ ad essere eseguita? O è una convenzione vecchia che si usa in algoritmi?
In java o altri linguaggi io farei $n^k$ senza chiedermi quanto ci impiega la macchina, sperando che il tempo sia bassissimo. In realtà non so quanto ci impiegano, $\log k$ sarebbe diciamo il classico tempo necessario n queste situazioni, o quello che si usa per convenzione negli algoritmi?

[vict85]

Dipende da che funzione usi per calcolarlo. Se usi un approccio naive, il tempo è \(k\), ma è semplice calcolarlo in \(\log k\). Penso che l'algoritmo fosse già conosciuto dai babilonesi. Esiste un limite teorico per questo tipo di operazione, e penso che tu lo possa trovare in The Art of Computer Programming di Knuth.

Detto questo l'esponenziale di un float è penso calcolato usando metodi diversi e suppongo tu possa considerare l'operazione come costante (seppure una costante molto maggiore di una somma o una moltiplicazione)

[absinth]

Grazie per la risposta, non conosco l'algoritmo di Knuth ma anche guardando semplicemente per ipotesi un [size=150]$k=2^i$[/size] se il prodotto tra due interi considero O(1) l'algoritmo diventa una banale ricorsione. Fatto sta che non so se in questa materia potevano darlo per scontato, magari ci sono algoritmi con prestazioni migliori che sono famosi?... però non è importante. Grazie per la conferma

[apatriarca]

Dipende anche molto dal contesto. Ad esempio, se stessimo parlando di una potenza di numeri in virgola mobile, allora il calcolo può essere fatto in tempo costante (calcolando \(x^y = 2^{y\,\log_2\,x}\)). Per numeri interi si usa il già citato algoritmo. Per numeri di dimensione arbitraria esistono poi algoritmi ancora piú complessi e la moltiplicazione stessa non ha piú un tempo costante.

[absinth]

Grazie mille!