Le equazioni di ricorrenza esprimono la complessità temporale degli algoritmi ricorsivi. Non si può calcolare normalmente la complessità di questi algoritmi dato che la loro funzione di costo computazionale è anch’essa ricorsiva.
Esempio:
def ricercaR(x, A, i=0):
if len(A) == i:
return None
if A[i] == x:
return i
else:
return ricercaR(x, A, i+1)Equazione di complessità
Metodi di risoluzione
Esempi di equazioni di ricorrenza a partire da programmi
Esempio con il fattoriale
def fattoriale(n):
if n==0: # caso base
return 1
return n * fattoriale(n-1) # passo ricorsivo- Il tempo dipende da :
- Il caso base costa e si calcola con le classiche regole della complessità temporale
- Il caso ricorsivo costa
Risolvendo l’equazione di ricorrenza, la complessità del programma risulta .
Esempio con la somma delle liste
def somma(A):
if not len(A):
return 0
return A[0] + somma(A[1:])Il è dovuto allo slicing nel passo ricorsivo.
Ottimizzazione
Dato che la complessità del passo ricorsivo è dovuto allo slicing della lista, per ottimizzare l’algoritmo basta passare sempre la lista originare alla chiamata ricorsiva, ma incrementando l’indice a ogni iterazione.
def somma(A, i=0):
if A == i:
return 0
return A[i] + somma(A, i+1)