Ich habe hoch und niedrig gesucht und kann nicht viel Material finden, das sich auf Laufzeitkomplexitäten, Rekursion und Java bezieht.
Ich lerne gerade Laufzeit-Komplexitäten und Big-O-Notation in meiner Algorithms-Klasse, und ich habe Probleme, rekursive Algorithmen zu analysieren.
%Vor%Dies ist eine rekursive Methode, die einfach durch eine doppelt verknüpfte Liste iteriert und die Elemente ausdruckt.
Das Einzige, was ich mir vorstellen kann, ist, dass es eine Laufzeitkomplexität von O (n) hat, da die Anzahl der rekursiven Methodenaufrufe von der Anzahl der Knoten in der DList abhängt, aber immer noch nicht fühle mich wohl mit dieser Antwort.
Ich bin nicht sicher, ob ich den Zusatz von d und d.getNext() berücksichtigen sollte.
Oder bin ich einfach völlig daneben und die Komplexität der Laufzeit ist konstant, da alle Elemente aus dem DNodes in DList ?
Auf den ersten Blick sieht das aus wie ein klassischer Fall von Schwanzrekursion modulo contras , einer Verallgemeinerung des Schwanzes Anruf. Es entspricht einer Schleife mit der Anzahl der Iterationen.
Es ist jedoch nicht so einfach: Die schwierigste Sache ist hier das Hinzufügen von d.getElement() zu einer wachsenden Zeichenkette: Dies ist an sich eine lineare Operation, und es wird N mal wiederholt . Daher ist die Komplexität Ihrer Funktion O(N^2) .
Dies ist ein ziemlich einfaches Beispiel, aber der Trick besteht darin, eine Wiederholungsrelation zu definieren, die eine Funktion der Laufzeit einer gegebenen Eingabegröße in Bezug auf kleinere Eingabegrößen ist. In diesem Beispiel würde unter der Annahme, dass die in jedem Schritt geleistete Arbeit die konstante Zeit C nimmt und angenommen wird, dass der Basisfall nicht funktioniert, dies folgendermaßen aussehen:
%Vor%Sie können dann mithilfe von Substitution nach Laufzeit suchen:
%Vor%Nach der Definition von O ist diese Gleichung O (n). Dieses Beispiel ist nicht besonders interessant, aber wenn Sie etwas wie die Laufzeit von Mergesort oder einen anderen Divide and Conquer-Algorithmus betrachten, können Sie eine bessere Vorstellung von Wiederholungsrelationen erhalten.
Wenn T (n) die Anzahl der elementaren Operationen ist (in diesem Fall - wenn wir den Körper der Funktion eingeben, wird eine der Linien innerhalb der Funktion höchstens einmal ausgeführt und alle außer der zweiten Rückkehr sind nicht O (1) ) ausgeführt durch Aufrufen von toStringRec in einer Liste von n Elementen, dann
%Vor%An dieser Stelle haben wir die Komplexität des Algorithmus beschrieben. Wir können nun die geschlossene Form für T, T (n) = O (n ** 2) berechnen.
Der Algorithmus hat eine Laufzeitkomplexität von O (n), wie Sie vorschlagen. Ihre Liste enthält n Elemente, und der Algorithmus wird für jedes Element eine fast feste Menge an Arbeit erledigen (das sind Element- und Next-Zugriffe sowie ein neuer toStringRec-Aufruf). Das Abrufen eines Elements von einem DNode dauert konstant, und konstante Zeiten werden in der Groß-O-Notation verworfen.
Das Interessante an rekursiven Methoden ist (in den meisten Fällen), dass sie auch O (n) in der Komplexität des Raums sind. Ein neuer Stapeleintrag (zum Speichern der an die Methode übergebenen Parameter) wird für jeden Aufruf von toStringRec erstellt, der n mal aufgerufen wird.
Für solche rekursiven Algorithmen ist es normalerweise möglich, eine rekursive Gleichung zu schreiben, um die Reihenfolge zu berechnen. Es ist üblich, die Anzahl der mit T (n) ausgeführten Befehle anzuzeigen. In diesem Beispiel haben wir:
T (n) = T (n - 1) + O (1)
(Angenommen, die Funktion getElement läuft in konstanter Zeit.) Die Lösung dieser Gleichung ist trivialerweise T (n) = O (n).
Das war der allgemeine Fall. Manchmal können Sie jedoch den Algorithmus analysieren, ohne eine solche Gleichung zu schreiben. In diesem Beispiel können Sie leicht argumentieren, dass auf jedes Element maximal einmal zugegriffen wird, und jedes Mal, wenn eine konstante Zeitarbeit ausgeführt wird; Also, es braucht O (n) insgesamt, um die Arbeit zu erledigen.
Tags und Links java recursion time-complexity big-o tailrecursion-modulo-cons