Complessità: fattoriale

Vedi esercizio numero 12 di pagina 202 del libro di testo

Versione iterativa

Osserva: il ciclo while si ripete n-1 volte

def f(n):                      # f1
    prodotto = 1               # f2
    i = 2                      # f3   
    while(i <= n):             # f4
        prodotto = prodotto*i  # f5
        i = i+1                # f6  
    return prodotto            # f7
  
n = int(input("n = "))         # c1 
x = f(n)                       # c2
print("Il fattoriale di", n, "=", x)  # c3

T(n) = $c_1 + c_2 + [\dots] + c_3$
= $c_1 + c_2 + [f_1+f_2+f_3 + [\dots] + f_7] + c_3$
= $c_1 + c_2 + [f_1+f_2+f_3 + [(f_4+f_5+f_6)\cdot (n-1) + f_4] + f_7] + c_3$
= $1 + 1 + [1+1+1 + [(1+1+1)\cdot (n-1) + 1] + 1] + 1$
= …
= $3\cdot n + 5$

Versione ricorsiva

def f(n):                # f1
    if(n < 2):           # f2
        return 1         # f3
    else:          
        return n*f(n-1)  # f4

n = int(input("n = "))   # c1 
x = f(n)                 # c2
print("Il fattoriale di", n, "=", x)  # c3

Prova per n=0, n=1, …

T(0) = $c_1 + c_2 + [\dots] + c_3$ = $c_1 + c_2 + [f_1+f_2+f_3] + c_3$ = 6
T(1) = $c_1 + c_2 + [\dots] + c_3$ = $c_1 + c_2 + [f_1+f_2+f_3] + c_3$ = 6
T(2) = $c_1 + c_2 + [\dots] + c_3$ = $c_1 + c_2 + [f_1+f_2+f_4 + [\dots]] + c_3$
= $c_1 + c_2 + [f_1+f_2+f_4 + [f_1+f_2+f_3] + c_3$ = 9
T(3) = $c_1 + c_2 + [\dots] + c_3$ = $c_1 + c_2 + [f_1+f_2+f_4 + [\dots]] + c_3$
= $c_1 + c_2 + [f_1+f_2+f_4 + [f_1+f_2+f_4+[\dots]] + c_3$
= $c_1 + c_2 + [f_1+f_2+f_4 + [f_1+f_2+f_4+[f_1+f_2+f_3]] + c_3$ = 12
…

Se n = 0: T(n) = 6
Se n > 0: T(n) = $3\cdot n+3$

La ricorsione sostituisce l’iterazione e

non cambia significativamente il tempo di esecuzione, lineare
il costo $f_4$ riassume una sottrazione, un prodotto, …
nella ricorsione ci sono i tempi di chiamata e ritorno che possono essere significativi
In alcune piattaforme c’è un limite massimo al livello di ricorsione.

Versione con formula

$\displaystyle n! \approx \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$

T(n) = $c_1 + c_2 + c_3 + c_4 + c_5 + c_6$ = 6

Vengono eseguite 6 operazioni molto diverse tra loro (prodotto, radice quadrata, …) ma il numero è costante.
Al crescere di n il calcolo della radice quadrata e della potenza hanno costo logaritmico.

Confronto

Consideriamo i pro e i contro di ognuno

Algoritmo	T(n)	O(f(n))	Pro	Contro
Iterativo	$c_{11}\cdot n + c_{12}$	$O(n)$	Codifica semplice	~n moltiplicazioni
Ricorsivo	$c_{21}\cdot n + c_{22}$	$O(n)$	Codifica molto corta	~n moltiplicazioni ~n chiamate ricorsive
Con formula	$c_{3}$ $c_{41}\log n + c_{42}$	$O(1)$ $O(\log n)$	Numero di operazioni molto basso	1. Difficile da ricordare 2. Numeri irrazionali 3. Valore approssimato

Conclusioni

Per il calcolo del fattoriale di n esistono più algoritmi
Le complessità in tempo sono …
Le complessità in tempo asintotiche sono …
Quale algoritmo scegliere al variare di n?
- Algoritmo ricorsivo
- Algoritmo iterativo, entrambi convenienti
- Con formula, solamente se n è mooolto grande perché il risultato è approssimato.