Qualunque operazione non dipendente dal numero di elementi viene considerata a costo costante, e visto che in notazione O-grande (e compagnia) tutto è definito a meno di costante moltiplicativa, tutte le costanti valgono 1.Originariamente inviata da stefano86
T(n-1) è la chiamata a permutazioni(listaDegliAltri) (listaDegliAltri è lunga n-1)T(n) = n(T(n-1) + (n-1)) per n > 1
+ (n-1) credo lo faccia venire dalla costruzione di listaDegliAltri (visto che va a costruire una lista di n-1 elementi)
L'n che moltiplica tutto deriva dal fatto che queste due operazioni vengono eseguite n volte (for i in range(n))
Non capisco però, se ha considerato la costruzione di listaDegliAltri, perché ignora la costruzione di risult (che è (n-1)!); in ogni caso, dato che dopo va a fare una maggiorazione, non è importante.
Ovvio, T(n) = n(T(n-1) + (n-1)), che è ovviamente maggiore di n*T(n-1) (ha tolto un termine sicuramente positivo dalla parentesi)Poi dice che sceglie la delimitazione inferiore e quindi scrive: (da qui in poi non ho capito più nulla)
T(n) > n*T(n-1)
Qui sta espandendo ricorsivamente la relazione che ha trovato prima.T(n) > n*T(n-1) > n*(n-1)*T(n-2) > n*(n-1)*(n-2)*T(n-3) > ... > n!
Lui sta cercando un limite inferiore di costo di questa funzione (ovvero, vuole mostrare che questa funzione è sicuramente più complessa di un'altra); tutto il giochino è trovare una maggiorazione "comoda" - ovvero, dalla relazione di ricorrenza relativa alla complessità "vera" della funzione costruisce una relazione di maggiorazione (T(n) > qualcosa) più comoda da manipolare, da cui alla fine ricava una relazione non ricorsiva semplice (T(n) > n!).Cioè:
T(n) = Ω(n!)
Non ho capito perchè ha eliminato l'(n-1) e perchè ha messo il maggiore invece dell'uguale. Insomma non ho capito nulla.
Rispondi quotando