[Algoritmi] Complessità

[stefano86]

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[i]
         listaDegliAltri = list[:i] + list[i + 1:]  
         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, a, c], [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 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:
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) = Ω(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]

Qualcuno sa aiutarmi?

[MItaly]

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