Come calcolare la complessità di una funzione ricorsiva?

Question

Qual è il modo più intuitivo per calcolare la complessità di tempo e spazio (notazione O grande) della seguente funzione ricorsiva?

function count(str) { 
    if (str.length <= 1) { 
    return 1; 
    } 

    var firstTwoDigits = parseInt(str.slice(0, 2), 10); 

    if (firstTwoDigits <= 26) { 
    return count(str.slice(1)) + 
      count(str.slice(2)); 
    } 

    return count(str.slice(1)); 
} 

Answer 1

Mi scuso per la mia risposta prev, Complessità del codice sembra essere

O (2^N) o O (2^N-1) per la precisione nel peggiore dei casi .

Quindi, se

N = str.length ;//number of iteration 

Nel peggiore dei casi, la vostra str si compone di tutte le cifre N di 1 o 2.

Poi, se N è 20 per cominciare, poi si pongono due più chiamate ricorsive di N = 18 e N = 19,

Poi, N = 19 genererà altre due chiamate (e quindi un valore fino a N è 0)

Quindi, il numero di chiamate aumenterà in modo esponenziale con ogni iterazione), quindi arrivando al valore (2^N - 1).