Time and Space Complessità

Question

Ho un dubbio relativo al tempo e alla complessità spaziale nel seguente 2 caso

.

Blockquote

Caso I:

Ricrezione: calcolo fattoriale.

int fact(int n)
{
    if(n==0)
      return 1;
    else
      return (n*fact(n-1));
}

.

Qui come mai la complessità del tempo diventa 2 * n e la complessità spaziale proporzionale a n.

e

.

Caso II:

Iterativo: -

int fact(int n)
{
    int i, result = 1;
    if(n==0)
    result = 1;
    else
         {
           for(1=1;i<=n;i++)
              result*=i;
         }
     return (result);
}

.

La complessità del tempo proporzionale a N e la complessità spaziale è costante. Questo rimanga sempre confuso per me.

Answer 1

Se il mio ragionamento è difettoso, qualcuno per favore correggimi :)

Per la complessità spaziale, ecco la mia spiegazione:

Per la soluzione ricorsiva, ci saranno chiamate ricorsive n, quindi ci saranno pile di generazione di n utilizzate; uno per ogni chiamata. Da qui lo spazio O(n). Questo non è il caso della soluzione iterativa - c'è solo una pila e non usi nemmeno un array, c'è solo una variabile. Quindi la complessità spaziale è O(1).

Per la complessità del tempo della soluzione iterativa, si dispone di moltiplicazioni n nel ciclo for, quindi un legato allentato sarà O(n). Ogni altra operazione può essere presunta di essere un'unità o tempo costante, senza alcun cuscinetto sull'efficienza complessiva dell'algoritmo. Per la soluzione ricorsiva, non ne sono così sicuro. Se ci sono due chiamate ricorsive ad ogni passaggio, è possibile pensare all'intera pila di chiamata come albero binario equilibrato, e il numero totale di nodi sarà 2*n - 1, ma in questo caso non sono così sicuro.

Answer 2

Da: https://cs.nyu.edu/ ~acase/FA14 / CS2 / Module_extras.php

Spazio complessità

Di seguito andremo a confrontare tre chiamate diverse sia alle funzioni fattative iterative che ricorsive e vediamo come viene utilizzata la memoria.Tieni presente che ogni variabile che dichiariamo deve avere spazio riservato in memoria per memorizzare i suoi dati.Quindi la complessità spaziale di un algoritmo nella sua forma più semplice è il numero di variabili in uso.Quindi in questa situazione più semplice possiamo calcolare la complessità spaziale approssimativa usando questa equazione:

Complessità spaziale= Numero di chiamate di funzione * Numero di variabili per chiamata

Answer 3

Complessità del tempo: il numero di istruzioni (macchina) che un programma esegue durante il suo tempo di esecuzione è chiamato la sua complessità del tempo in Computer Science.

Complessità spaziale: questo è essenzialmente il numero di celle di memoria con cui un algoritmo ha bisogno.

Caso 1: nel programma è di calcolare ricorsivamente il fattoriale, quindi ci sarà una chiamata diretta alla funzione e che ci sarà backtracking, quindi la complessità del tempo diventa 2 * n.

Parlare della complessità spaziale Ci saranno n pile dichiarate durante il punto di esecuzione del programma, quindi è n.

Caso 2: Questo caso è piuttosto semplice qui hai n iterazione all'interno del ciclo per il ciclo così la complessità del tempo è n

Questo non è il caso della soluzione iterativa - c'è solo una pila e non usi nemmeno un array, c'è solo una variabile.Quindi la complessità spaziale è o (1)