Wie berechnet man die Komplexität einer rekursiven Funktion?

Question

Was ist die intuitivste Art, die Komplexität von Zeit und Raum (Big-O-Notation) der folgenden rekursiven Funktion zu berechnen?

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

Entschuldigt meine vorherige Antwort, Komplexität des Codes scheint in schlimmsten Fall

O (2^N) oder O (2^N-1) sein um genau zu sein .

Also, wenn

N = str.length ;//number of iteration 

Im schlimmsten Fall Ihre str besteht aus allen N Ziffern von 1 oder 2.

Dann Wenn N 20 beginnen mit, dann es wird zwei weitere rekursive Aufrufe von N = 18 und N = 19, laichen

Dann N = 19 spawnen zwei weitere Aufrufe (und so ist ein bis Wert von N 0)

So wird die Anzahl der Aufrufe mit jeder Iteration exponentiell steigen), so dass auf den Wert (2^N - 1).