Complessità di run-time per algoritmi ricorsivi

Question

Ho cercato in alto e in basso e non riesco a trovare molto materiale relativo a complessità di run-time, ricorsione e java.

Attualmente sto imparando le complessità di run-time e la notazione Big-O nella mia classe Algorithms e sto riscontrando problemi nell'analisi degli algoritmi ricorsivi.

private String toStringRec(DNode d) 
{ 
    if (d == trailer) 
     return ""; 
    else 
     return d.getElement() + toStringRec(d.getNext()); 
} 

Questo è un metodo ricorsivo che semplicemente eseguirà l'iterazione attraverso una lista doppiamente collegata e stamperà gli elementi.

L'unica cosa che posso venire con è che ha una complessità di run-time di O (n), dal momento che il numero di chiamate metodo ricorsivo dipenderà dal numero di nodi nel dlist, ma ho ancora don' t sentirsi a proprio agio con questa risposta.

Non sono sicuro di dover calcolare l'aggiunta di d e d.getNext().

Oppure sono completamente fuori strada e la complessità del tempo di esecuzione è costante, poiché tutto ciò che sta facendo è recuperare elementi dallo DNodes nello DList?

Answer 1

L'algoritmo presenta la complessità di runtime di O (n) come suggerito. L'elenco contiene n elementi e l'algoritmo eseguirà una quantità di lavoro quasi obbligata per ciascun elemento (che funziona come accesso Element e Next, oltre a una nuova chiamata toStringRec). Il recupero di un elemento da un DNode richiede tempo costante e i tempi costanti vengono scartati nella notazione O grande.

La cosa interessante dei metodi ricorsivi (nella maggior parte dei casi) è che anch'essi sono anche O (n) nella complessità dello spazio. Una nuova voce di stack (per memorizzare i parametri passati al metodo) viene creata per ogni chiamata a toStringRec, che viene chiamata n volte.

Answer 2

A prima vista, questo sembra un classico caso di tail recursion modulo cons, una generalizzazione di coda chiamata. È equivalente a un ciclo con il numero di iterazioni.

Tuttavia, non è così semplice: la cosa difficile qui è l'aggiunta di d.getElement() in una stringa in crescita: questo è di per sé un lineare operazione , e si ripete N volte. Quindi la complessità della tua funzione è O(N^2).

Answer 3

Se T (n) è il numero di operazioni elementari (in questo caso - quando si entra nel corpo della funzione, una delle righe all'interno sono eseguiti al massimo una volta per tutte, ma il secondo ritorno non è O (1)) eseguito chiamando toStringRec su un elenco di n elementi, quindi

T(0) = 1 - as the only things that happen is the branch instruction and a 
       return 
    T(n) = n + T(n-1) for n > 0 - as the stuff which is being done in the 
       function besides calling toStringRec is some constant time stuff and 
       concatenating strings that takes O(n) time; and we also run 
       toStringRec(d.getNet()) which takes T(n-1) time 

a questo punto abbiamo descritto la complessità dell'algoritmo. Ora possiamo calcolare la forma chiusa per T, T (n) = O (n ** 2).

Answer 4

Questo è un esempio piuttosto semplice, ma il trucco è definire una relazione di ricorrenza, che è una funzione del tempo di esecuzione di una determinata dimensione di input in termini di dimensioni di input più piccole.Per questo esempio, supponendo che il lavoro svolto ad ogni passo richiede costante di tempo C e supponendo che il caso base non lavora, sarebbe:

T(0) = 0 
T(n) = C + T(n-1) 

È quindi possibile risolvere per l'esecuzione tempo con sostituzione di trovare una serie :

T(n) = C + T(n-1) = 2C + T(n-2) = 3C + T(n-3) = ... = nC + T(n-n) = nC + 0 = nC 

Con la definizione di O, questa equazione è O (n). Questo esempio non è particolarmente interessante, ma se si guarda qualcosa come il runtime di mergesort o un altro algoritmo di divisione e conquista è possibile ottenere un'idea migliore delle relazioni di ricorrenza.

Answer 5

Per tali algoritmi ricorsivi, è in genere possibile scrivere un'equazione ricorsiva per calcolare l'ordine. È consuetudine mostrare il numero di istruzioni eseguite con T (n). In questo esempio, abbiamo:

T (n) = T (n - 1) + O (1)

(Supponendo che la funzione getElement gira in tempo costante.) La soluzione di questa equazione è banalmente T (n) = O (n).

Questo era il caso generale. Tuttavia, a volte è possibile analizzare l'algoritmo senza scrivere tale equazione. In questo esempio, puoi facilmente sostenere che ogni elemento è visitato al massimo una volta, e ogni volta che viene eseguito un lavoro a tempo costante; quindi, occore O (n) nel complesso per fare il lavoro.