PDA

Visualizza la versione completa : [Algoritmi] Complessità


stefano86
06-04-2015, 14:56
Ciao a tutti, ho difficoltà a capire come si arriva a determinare la complessità temporale di questo algoritmo (è scritto in Python, ma andrebbe bene qualsiasi linguaggio):


def permutazioni(list):
n = len(list)
if n == 1 or n == 0:
return
[list]
else:
risult = []
for i in range(n):
primo = list
listaDegliAltri = list[:i] + list
perms = permutazioni(listaDegliAltri)
for perm in perms:
risult.append([primo] + perm)
return risult


Questa procedura prende in input una sequenza e restituisce come risultato una sequenza di sequenze contenente l'insieme di tutte le possibili permutazioni della sequenza di partenza.

Esempio: permutazioni([a, b, c]) = [ [a, b, c], [a, c, b], , [b, c, a], [c, a, b], [c, b, a] ]

Ora, per determinare la complessità, devo scrivere e risolvere l'equazione di ricorrenza.
Quando la lista è lunga [I]0 o 1, non si effettuano operazioni.
Altrimenti, si esegue un ciclo di n iterazioni in cui ad ogni iterazione la funzione viene richiamata su una lista con un elemento in meno (n-1) e poi si esegue un for interno lungo n-1.

Il professore quindi ha scritto:
[I]T(0) = T(1) = 1 (Perchè 1? E' il costo del return o di altro?)
T(n) = n(T(n-1) + (n-1)) per n > 1
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)
da cui:
T(n) > n*T(n-1) > n*(n-1)*T(n-2) > n*(n-1)*(n-2)*T(n-3) > ... > n!
Cioè:
T(n) = [B]Ω(n!)
Non ho capito perchè ha eliminato l'(n-1) e perchè ha messo il maggiore invece dell'uguale. Insomma non ho capito nulla.
Qualcuno saprebbe spiegarmelo?
Grazie :)

stefano86
08-04-2015, 20:32
Qualcuno sa aiutarmi? :)

MItaly
09-04-2015, 13:49
T(0) = T(1) = 1 (Perchè 1? E' il costo del return o di altro?)
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.


T(n) = n(T(n-1) + (n-1)) per n > 1
T(n-1) è la chiamata a permutazioni(listaDegliAltri) (listaDegliAltri è lunga 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.


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)
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)


T(n) > n*T(n-1) > n*(n-1)*T(n-2) > n*(n-1)*(n-2)*T(n-3) > ... > n!

Qui sta espandendo ricorsivamente la relazione che ha trovato prima.

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.

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!).

Loading