Come posso calcolare la complessità temporale di un algoritmo ricorsivo?
int pow1(int x,int n) { if(n==0){ return 1; } else{ return x * pow1(x, n-1); } } int pow2(int x,int n) { if(n==0){ return 1; } else if(n&1){ int p = pow2(x, (n-1)/2) return x * p * p; } else { int p = pow2(x, n/2) return p * p; } }
Analizzare le funzioni ricorsive (o anche valutarle) è un compito non banale. A (secondo me) una buona introduzione può essere trovata in Don Knuths Concrete Mathematics .
Tuttavia, analizziamo questi esempi ora:
Definiamo una funzione che ci dà il tempo necessario per una funzione. Diciamo che t(n)
denota il tempo richiesto da pow(x,n)
, cioè una funzione di n
.
Quindi possiamo concludere, che t(0)=c
, perché se chiamiamo pow(x,0)
, dobbiamo controllare se ( n==0
), e quindi restituire 1, che può essere fatto in tempo costante (quindi la costante c
).
Ora consideriamo l’altro caso: n>0
. Qui otteniamo t(n) = d + t(n-1)
. Questo perché dobbiamo ancora controllare n==1
, calcolare pow(x, n-1
, quindi ( t(n-1)
) e moltiplicare il risultato per x
. Il controllo e la moltiplicazione possono essere eseguiti in tempo costante (costante d
), il calcolo ricorsivo di pow
bisogno di t(n-1)
.
Ora possiamo “espandere” il termine t(n)
:
t(n) = d + t(n-1) = d + (d + t(n-2)) = d + d + t(n-2) = d + d + d + t(n-3) = ... = d + d + d + ... + t(1) = d + d + d + ... + c
Quindi, quanto ci vuole prima che raggiungiamo t(1)
? Dato che iniziamo con t(n)
e sottraiamo 1 in ogni passo, ci vogliono n-1
passi per raggiungere t(n-(n-1)) = t(1)
. Questo, d’altra parte, significa che otteniamo n-1
volte la costante d
, e t(1)
è valutata a c
.
Quindi otteniamo:
t(n) = ... d + d + d + ... + c = (n-1) * d + c
Quindi otteniamo che t(n)=(n-1) * d + c
che è l’elemento di O (n).
pow2
può essere fatto usando il teorema di Masters . Dal momento che possiamo assumere che le funzioni temporali per gli algoritmi stiano aumentando monotonicamente. Quindi ora abbiamo il tempo t(n)
necessario per il calcolo di pow2(x,n)
:
t(0) = c (since constant time needed for computation of pow(x,0))
per n>0
otteniamo
/ t((n-1)/2) + d if n is odd (d is constant cost) t(n) = < \ t(n/2) + d if n is even (d is constant cost)
Quanto sopra può essere "semplificato" per:
t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)
Quindi otteniamo t(n) <= t(n/2) + d
, che può essere risolto usando il teorema dei maestri a t(n) = O(log n)
(vedere la sezione Applicazione agli algoritmi più popolari nel collegamento wikipedia, esempio "Ricerca binaria").
Iniziamo con pow1, perché è il più semplice.
Hai una funzione in cui una singola esecuzione viene eseguita in O (1). (Il controllo delle condizioni, il ritorno e la moltiplicazione sono costanti).
Ciò che ti rimane è quindi la tua ricorsione. Quello che devi fare è analizzare quanto spesso la funzione finirà per chiamarsi. In pow1, succederà N volte. N * O (1) = O (N).
Per pow2, è lo stesso principio: una singola esecuzione della funzione viene eseguita in O (1). Tuttavia, questa volta stai dimezzando N ogni volta. Ciò significa che verrà eseguito log2 (N) volte – efficacemente una volta per bit. log2 (N) * O (1) = O (log (N)).
Qualcosa che potrebbe aiutarti è sfruttare il fatto che la ricorsione può sempre essere espressa come iterazione (non sempre molto semplicemente, ma è ansible. Possiamo esprimere pow1 come
result = 1; while(n != 0) { result = result*n; n = n - 1; }
Ora hai invece un algoritmo iterativo e potresti trovare più facile analizzarlo in questo modo.
Può essere un po ‘complesso, ma penso che il modo usuale sia usare il teorema del Maestro .
La complessità di entrambe le funzioni che ignorano la ricorsione è O (1)
Per il primo algoritmo pow1 (x, n) la complessità è O (n) perché la profondità della ricorsione è correlata con n in modo lineare.
Per la seconda complessità è O (log n). Qui riceviamo circa log2 (n) volte. Buttando fuori 2 otteniamo il registro n.
Quindi immagino che stai aumentando x alla potenza n. pow1 richiede O (n).
Non cambi mai il valore di x ma prendi 1 da n ogni volta fino a che non arriva a 1 (e poi torni indietro) Ciò significa che effettuerai una chiamata ricorsiva n volte.