Tempo di esecuzione con Notazione grande 01

Question

def filter(f, lst):  
    if lst == []: return [] 
    if f(lst[0]): return [lst[0]] + filter(f, lst[1:]) 
    return filter(f, lst[1:]) 

def my_reverse(lst):  # Reverse the list 
    def reverse_helper(x,y): 
     if x == []: return y 
     return reverse_helper(x[1:], [x[0]] + y) 
    return reverse_helper(lst, []) 

def revfilter_alpha(f, lst): # Reverse and filter ... 
    return my_reverse(filter(f, lst)) 

def revfilter_beta(f, lst): # Reverse and filter ... 
    if lst == []: return [] 
    return revfilter_beta(f, lst[1:]) + ([lst[0]] if f(lst[0]) else []) 

Qualcuno potrebbe spiegarmi come determinare il tempo di esecuzione in notazione Big for per questi? Ho letto un bel po 'di cose ma non ho ancora idea da dove cominciare.

In filter, penso che sia Θ (n^2) perché controlla ogni elemento nell'elenco di dimensioni n con la funzione predicato f con n chiamate ricorsive quindi n * n.

revfilter_beta sembra piuttosto simile invertendo semplicemente durante il filtraggio, quindi non sarebbe anche questo Θ (n^2)?

revfilter_alpha filtra quindi un reverse, quindi non sarebbe n^2 * n^2 = Θ (n^4)?

Qualcuno ha qualche idea?

Answer 1

filter ha n chiamate ricorsive, ma anche eseguire un'operazione di copia su ogni iterazione che prende n, quindi si finisce per avere Θ (n^2). Se lo hai implementato correttamente, dovrebbe essere Θ (n).

Uguale a my_reverse.

Uguale a revfilter_beta.

revfilter_alpha fa solo un filter e quindi un reverse, quindi questo n (n^2 + n^2) = Θ (n^2).

---

EDIT: Vediamo in filter un po 'di più.

Quello che si vuole capire è il numero di operazioni eseguite rispetto alla dimensione dell'input. O(n) significa che, nel peggiore dei casi, si eseguirà l'ordine delle operazioni n. Dico "sull'ordine di" perché potresti, ad esempio, fare operazioni O(n/2) o O(4n), ma il fattore più importante è n. Cioè, man mano che cresce n, il fattore costante diventa sempre meno importante, quindi guardiamo solo il fattore non costante (n in questo caso).

Quindi, quante operazioni esegue filter in un elenco di dimensioni n?

Prendiamolo dal basso verso l'alto. Cosa succede se n è 0 - una lista vuota? Quindi restituirà solo una lista vuota. Quindi diciamo che è 1 operazione.

Cosa succede se n è 1? Verificherà se deve essere incluso lst[0] - che il controllo impiega il tempo necessario per chiamare f - e quindi copierà il resto dell'elenco e farà una chiamata ricorsiva su quella copia, che in questo caso è una lista vuota. quindi filter(1) prende le operazioni f + copy(0) + filter(0), dove copy(n) è il tempo necessario per copiare un elenco e f è il tempo necessario per verificare se un elemento deve essere incluso, presupponendo che richieda lo stesso tempo per ciascun elemento.

Che dire di filter(2)? Effettua 1 controllo, quindi copia il resto dell'elenco e chiama filter sul resto: f + copy(1) + filter(1).

È già possibile vedere lo schema.filter(n) prende 1 + copy(n-1) + filter(n-1).

Ora, copy(n) è solo n - occorrono le operazioni n per suddividere l'elenco in questo modo. Quindi possiamo semplificare ulteriormente: filter(n) = f + n-1 + filter(n-1).

Ora si può provare solo espansione fuori filter(n-1) un paio di volte per vedere cosa succede:

filter(n) = f + n-1 + filter(n-1) 
      = 1 + n-1 + (f + n-2 + filter(n-2)) 
      = f + n-1 + f + n-2 + filter(n-2) 
      = 2f + 2n-3 + filter(n-2) 
      = 2f + 2n-3 + (f + n-3 + filter(n-3)) 
      = 3f + 3n-6 + filter(n-3) 
      = 3f + 3n-6 + (f + n-4 + filter(n-4)) 
      = 4f + 4n-10 + filter(n-4) 
      = 5f + 5n-15 + filter(n-5) 
      ... 

Possiamo generalizzare per x ripetizioni? Quella 1, 3, 6, 10, 15 ... sequenza è il numero triangolo - che è, 1, 1+2, 1+2+3, 1+2+3+4, ecc La somma di tutti i numeri 1-x è x*(x-1)/2.

  = x*f + x*n - x*(x-1)/2 + filter(n-x) 

Ora, che cos'è x? Quante ripetizioni avremo? Bene, puoi vedere che quando x = n, non hai più ricorsione - filter(n-n) = filter(0) = 1. Quindi la nostra formula è ora:

filter(n) = n*f + n*n - n*(n-1)/2 + 1 

cui possiamo semplificare ulteriormente:

filter(n) = n*f + n^2 - (n^2 - n)/2 + 1 
      = n*f + n^2 - n^2/2 + n/2 + 1 
      = n^2 - n^2/2 + f*n + n/2 + 1 
      = (1/2)n^2 + (f + 1/2)n + 1 

Quindi ci ya avete - un'analisi piuttosto dettagliata. Sarebbe Θ((1/2)n^2 + (f + 1/2)n + 1) ... supponendo che f sia insignificante (ad esempio f = 1) che arriva a Θ((1/2)n^2 + (3/2)n + 1).

Ora noterete, se copy(n) presero una quantità costante di tempo invece di un importo lineare del tempo (se copy(n) era 1 invece di n), allora non si otterrebbe quel termine n^2 in là.

Ammetto, quando ho detto inizialmente Θ(n^2), non ho fatto tutto questo nella mia testa. Piuttosto, ho pensato: ok, hai passaggi ricorsivi n, e ogni passo richiederà n quantità di tempo a causa dello copy. n*n = n^2, quindi Θ(n^2). Per fare questo un po 'più esattamente, n si restringe ad ogni passo, in modo da realmente avere n + (n-1) + (n-2) + (n-3) + ... + 1, che finisce per essere la stessa cifra di cui sopra: n*n - (1 + 2 + 3 + ... + n) = n*n - n*(n-1)/2 = (1/2)n^2 + (1/2)n, che è lo stesso se avessi usato 0 invece di f, sopra . Allo stesso modo, se avessi n passaggi ma ogni passo ha preso 1 invece di n (se non dovessi copiare l'elenco), allora avresti 1 + 1 + 1 + ... + 1, n volte, o semplicemente n.

Ma, ciò richiede un po 'più di intuizione, quindi ho pensato di mostrarti anche il metodo della forza bruta che puoi applicare a qualsiasi cosa.

Answer 2

Tutte le funzioni sono O(N^2) perché si prendono O(N) tempo per passo ricorsivo e ci saranno N passi su una lista di lunghezza N.

Ci sono due operazioni costose (ovvero O(N)) che si stanno svolgendo nelle proprie funzioni. Il primo è il taglio (ad esempio lst[1:]). Il secondo è la concatenazione di liste (usando l'operatore +).

Entrambi possono essere più costosi di quanto ci si aspetti, in gran parte perché gli elenchi di Python non sono come i tipi di dati elenco in altre lingue. Sotto il cofano sono matrici, non liste collegate. È possibile eseguire le operazioni di cui sopra sugli elenchi collegati in tempo O (1) (anche se lo O(1) slicing è distruttivo). In Lisp, ad esempio, gli algoritmi utilizzati sono O(N) anziché O(N^2).

La ricorsione è spesso anche non ottimale in Python perché non esiste tail call elimination. Il limite di ricorsione predefinito di Python è 1000 nelle versioni recenti, quindi lunghe liste interromperanno le soluzioni puramente ricorsive a meno che non si scherzi nel modulo sys per aumentare il limite.

È anche possibile eseguire una versione di questi algoritmi in Python, con lo O(N), ma è necessario evitare il più possibile le costose operazioni di elenco sopra. Piuttosto che ricorsivamente, suggerisco di usare i generatori, che sono uno stile di programmazione molto più "pitonico".

Il filtraggio con un generatore è molto semplice. La funzione built-in filter lo fa già, ma è possibile scrivere il proprio in poche righe:

def my_filter(f, iterable): 
    for e in iterable: 
     if f(e): 
      yield e 

Invertendo l'ordine delle cose è un po 'più complicato, dal momento che è necessario o essere in grado di fare casuale accedere all'origine o utilizzare lo spazio aggiuntivo O(N) (l'algoritmo utilizza lo stack per quello spazio, anche se le liste seguono il protocollo di sequenza e possono essere consultate in modo casuale). Il built-in reversed funzione funziona solo su sequenze, ma qui è una versione che funziona su qualsiasi iterabile (come un altro generatore):

def my_reversed(iterable): 
    storage = list(iterable) # consumes all the input! 
    for i in range(len(storage)-1, -1, -1): 
     yield storage[i] 

noti che diversamente molti generatori, questo su consuma tutto il suo ingresso in una volta prima inizia a produrre output. Non eseguirlo su un input infinito!

È possibile comporre questi in qualsiasi ordine, e my_reversed(filter(f, lst)) dovrebbe essere equivalente a filter(f, my_reversed(lst)) (anche se per quest'ultimo, è preferibile utilizzare la funzione integrata reversed).

Il tempo di esecuzione per entrambi i generatori sopra (e la loro composizione in entrambi gli ordini) sarà O(N).