Beweisen Sie Zeitkomplexität des rekursiven Algorithmus

Question

Ich habe einen rekursiven Algorithmus in einer Aufgabe gegeben, von dem ich beweisen muss, dass es eine gegebene Zeit-Komplexität hat.

Der Algorithmus ist wie folgt (in Java geschrieben)

int partDist(String w1, String w2, int w1len, int w2len) { 
    if (w1len == 0) 
     return w2len; 
    if (w2len == 0) 
     return w1len; 
    int res = partDist(w1, w2, w1len - 1, w2len - 1) + 
    (w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1); 
    int addLetter = partDist(w1, w2, w1len - 1, w2len) + 1; 
    if (addLetter < res) 
     res = addLetter; 
    int deleteLetter = partDist(w1, w2, w1len, w2len - 1) + 1; 
    if (deleteLetter < res) 
     res = deleteLetter; 
    return res; 

}

Die Zuordnung ist zu beweisen, dass dieser Algorithmus in die Tat die Zeitkomplexität Omega hat (2^max (n, m)) wobei n und m die Längen von w1 bzw. w2 sind. Mein Wissen in diesem Bereich ist spärlich, gelinde gesagt, aber ich habe es geschafft, eine video on youtube Analyse der Fibonacci-Sequenz-Rekursion ziemlich hilfreich zu finden.

Ich habe grundsätzlich versucht, die Lösung aus dem Video auf meinem Algorithmus rückwärts zu konstruieren, aber ich komme mit der zeitlichen Komplexität Omega (3^min (n, m)).

Die Art, wie ich zu dieser Schlussfolgerung gelangt bin, die keineswegs die korrekte Methode ist, ist, dass ich eine Art Untergrenze (ich denke?) Berechne, indem ich sage, dass T (n-1, m-1) = T (m, n-1) und T (m-1, n) (wie ich denke, das sind die anderen beiden Begriffe). Danach erweitere ich einfach die Formel um zwei oder drei Schritte und verallgemeinere es. Ich komme dann mit meiner Zeit Komplexität. Ich verstehe nicht, wie die Zeitkomplexität 2^(max (n, m)) sein kann, da es drei zusätzliche rekursive Aufrufe für jeden gibt, und ich verstehe auch nicht, warum es maximal und nicht min ist, wie die Methode ist linear (rechts?), wenn eine der beiden Längen Null ist.

Answer 1

muss die Laufzeit das erneute Auftreten

T(n, m) = T(n - 1, m - 1) + T(n, m - 1) + T(n - 1, m) + T 
T(0, m) = T' 
T(n, 0) = T" 

Eine Lösung mit einer Zweierpotenz ist unwahrscheinlich, da ein einziger Anruf beinhaltet drei indirekte Anrufe folgen.