Laufzeit des folgenden rekursiven Algorithmus?

Question

Ich arbeite durch das Buch "Cracking the Coding Interview" von Gayle McDowell und stieß auf einen interessanten rekursiven Algorithmus, der die Werte aller Knoten in einem ausgeglichenen binären Suchbaum summiert.

int sum(Node node) { 
if (node == null) { 
    return 0; 
} 
return sum(node.left) + node.value + sum(node.right); 
} 

Jetzt Gayle sagt die Laufzeit O (N) ist, die ich verwirrend finden, wie ich sehe nicht, wie dieser Algorithmus jemals enden wird. Für einen bestimmten Knoten, wenn node.left im ersten Aufruf zur Summe übergeben wird und dann node.right im zweiten Aufruf zur Summe weitergeleitet wird, berechnet der Algorithmus nicht die Summe (Knoten) zum zweiten Mal? Würde dieser Prozess nicht für immer weitergehen? Ich bin immer noch neu in rekursiven Algorithmen, so dass es vielleicht noch nicht sehr intuitiv ist.

Prost!

Answer 1

Der Prozess wird nicht für immer weitergehen. Die fragliche Datenstruktur ist ein balancierter binärer Suchbaum und kein Graph, der Zyklen enthalten kann.

Ausgehend von der Wurzel, werden alle Knoten in der Art und Weise untersucht - left -> itself -> right, wie eine Tiefe erste Suche.

node.left untersucht den linken Teilbaum eines Knotens und node.right wird den rechten Teilbaum des gleichen Knotens erkunden. Beide Teilbäume haben nichts schneidend. Zeichnen Sie die Spur der Programmsteuerung, um die Reihenfolge zu sehen, in der die Knoten erkundet werden, und um zu sehen, dass es keine Überlappung in der Traversierung gibt.

Da jeder Knoten nur einmal besucht wird, und die Rekursion beginnt Abwickeln, wenn ein Blattknoten getroffen wird, wird die Laufzeit O (N), N die Anzahl der Knoten ist.

Answer 2

Der Schlüssel zum Verständnis eines rekursiven Algorithmus besteht darin, darauf zu vertrauen, dass es das tut, was es für richtig hält. Lassen Sie mich erklären.

Geben Sie zuerst zu, dass die Funktion sum(node) die Summe der Werte aller Knoten des Teilbaums mit der Wurzel node zurückgibt.

Dann wird der Code

if (node == null) { 
    return 0; 
} 
return sum(node.left) + node.value + sum(node.right); 

können zwei Dinge tun:

1. wenn der Knoten null, Rückkehr 0 ist; Dies ist ein nicht rekursiver Fall und der zurückgegebene Wert ist trivialerweise korrekt.

2. Andernfalls berechnet die Funktionen erzeugen die Summe für den linken Unterbaum plus dem Wert bei node plus der Summe für den rechten Teilbaum, das heißt die Summe für den Teilbaum bei node verwurzelt.

So in einer Art und Weise, wenn die Funktion korrekt ist, dann ist es richtig :) Eigentlich ist das Argument nicht kreisförmig durch den nicht-rekursive Fall ist, was auch richtig ist.

---

Wir können die gleiche Art der Argumentation verwenden, um die Laufzeit des Algorithmus zu beweisen.

Angenommen, die Zeit, die für die Verarbeitung des am Knoten verwurzelten Baums erforderlich ist, ist proportional zur Größe dieses Teilbaums. Lassen Sie |T|. Dies ist ein weiterer Akt des Glaubens.

Dann, wenn node Null ist, ist die Zeit konstant, lassen Sie 1 Einheit. Und wenn node nicht null ist, ist die Zeit |L| + 1 + |R| Einheiten, die genau |T| ist. Wenn also die Zeit zum Aufsummieren eines Teilbaums proportional zur Größe des Teilbaums ist, ist die Zeit zum Aufsummieren eines Baums proportional zur Größe des Baums!