•  21-09-2019
  •  | 
  •  

Frage

Warum ist die Rekursion rekursive faktorielles Algorithmus das? 

T(n)=1 for n=0
T(n)=1+T(n-1) for n>0

Warum ist es nicht das? 

T(n)=1 for n=0
T(n)=n*T(n-1) for n>0

Einlochen Werte von n d.h 1,2,3,4 ...... das zweite Rekursion hält (Die factorials richtig berechnet) nicht der erste.

War es hilfreich?

Lösung

Diese Frage ist sehr verwirrend ... Sie erste Formel ist nicht faktoriell. Es ist einfach T (n) = n + 1 für alle n. Faktoriellen von n ist das Produkt der ersten n positiven ganzen Zahlen: faktoriellen (1) = 1. faktoriellen (n) = n * faktoriellen (n-1). Ihre zweite Formel ist im wesentlichen richtig.

Andere Tipps

Sieht aus wie T (n) die Rekursion der Zeitkomplexität des rekursiven faktorielles Algorithmus, unter der Annahme konstanter Zeit Multiplikation. Vielleicht falsch verstehen Sie Ihre Quelle?

Wir verwenden Rekursion im Allgemeinen die Zeitkomplexität des Algorithmus zu finden.

Hier ist die Funktion T (n) ist eigentlich nicht für den Wert eines faktoriellen Berechnung aber es wird Sie über die Zeitkomplexität des Fakultäts Algorithmus zu sagen.

Es bedeutet für die Suche nach einer Fakultät von n wird es 1 mehr Betrieb nehmen als Fakultäts von n-1 (D T (n) = T (n-1) + 1) und so weiter.

so richtig Rekursion für eine rekursive faktorielles Algorithmus T (n) = 1 für n = 0 T (n) = 1 + T (n-1) für n> 0 nicht, dass Sie später erwähnt wird.

wie Wiederholung für TvH ist T (n) = 2T (n-1) + 1 für n> 0;

Ich gehe davon aus, dass Sie schlechte Informationen. Die zweite Rekursion Sie zitieren ist die richtige, wie Sie beobachtet haben. Die erste erzeugt nur die natürlichen Zahlen.

Wo haben Sie die ersten? Es ist völlig falsch.

Es ist nur 1 jedes Mal hinzuzufügen gehen, was der Wert ist.

Was er brachte, nicht die Fakultäts Rekursion, aber die Zeit Komplexität davon.
Angenommen, dies ist der Pseudo-Code für eine solche Wiederholung: 

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)
  • Ich gehe davon aus, dass Schwanz-Rekursion Beseitigung nicht beteiligt ist.

Zeile 2 und 3 kostet eine konstante Zeit, C1 und C2.
Linie 4 kostet eine konstante Zeit als gut. Aber es ruft faktorielles (n-1), die einige Zeit T stattfinden wird (n-1). Auch nimmt die Zeit, es zu multiplizieren faktorielles (n-1) n ignoriert werden kann, wenn T (n-1) verwendet wird.
Zeit für die ganze Funktion ist nur die Summe: T (n) = C1 + C2 + T (n-1)
. Dies ist in big-o-Notation wird auf T reduziert (n) = 1 + T (n-1).

Dies ist, wie Diam ausgeführt hat, eine flache Rekursion ist also seine Laufzeit sollte O (n) sein. Seine Platzkomplexität wird enorm obwohl sein.

T (n) = T (n-1) + 1 richtig ist Rekursionsgleichung für faktorielle von n. Diese Gleichung gibt Ihnen die Zeit Faktorielle von NOT-Wert des Fakultäts von n zu berechnen.

Als erstes müssen Sie eine einfache Bedienung finden und für dieses Beispiel ist es Multiplikation. Multiplikation geschieht einmal in jeder Rekursion. Damit T (n) = T (n-1) +1 Dies ist +1 Grundbetrieb (mutliplication für dieses Beispiel) T (n-1) ist neben Rekursion Anruf.

TL; DR: Die Antwort auf Ihre Frage tatsächlich hängt von welcher Reihenfolge Ihre Rekursion ist definieren . Das heißt, ob die Sequenz T n in Frage stellt die Fakultätsfunktion oder die Laufzeitkosten für die Fakultäts-Funktion von Rechen X .

Die Fakultätsfunktion

Die rekursive Defintion der Fakultäts von n f n ist:

f n = n • f n-1 für n> 0 mit f < sub> 0 = 1 .

Wie Sie sehen können, über die Gleichung ist eigentlich ein Rekursion , da es sich um eine Gleichung ist, dass zusammen mit dem anfängliche Laufzeit (dh f 0 = 1 ) rekursiv definiert eine sequence (dh die faktorielle Funktion, f n ).

Modellierung der Laufzeitkosten für die Berechnung der Fakultäts

Nun werden wir ein Modell finden zur Darstellung der Laufzeitkosten für die Berechnung der Fakultät von n . Nennen wir T n die Laufzeit-Kosten der Berechnung f n .

Mit Blick auf die obige Definition der Fakultätsfunktion f n , dessen Laufzeit Kosten T n besteht aus den Laufzeitkosten wird von der Berechnung f n-1 (dh diese Kosten T n-1 ) sowie die Laufzeit Kosten für die Durchführung der Multiplikation zwischen n und f n-1 . Die Multiplikation wird in konstanter Zeit erreicht. Daher können wir sagen, dass T n = T n-1 + 1 .

Doch was ist der Wert von T 0 ? T 0 stellt die Laufzeitkosten für die Berechnung f 0 . Da der Wert von f 0 wird zunächst per Definition bekannt, die Laufzeitkosten für die Berechnung f 0 ist tatsächlich konstant. Daher könnte man sagen, dass T 0 = 1 .

Schließlich, was wir erhalten, ist:

T n = T n-1 + 1 für n> 0 mit T < sub> 0 = 1 .

Diese Gleichung oben ist auch eine Rekursion . Doch was sie (zusammen mit der ersten Laufzeit) definieren, ist eine Sequenz, die Modelle der Laufzeitkosten für die Berechnung der Fakultätsfunktion .

X Unter Berücksichtigung, wie die Sequenz in Ihrem Rekursion genannt wird (dh T n ), ich denke, es sehr stellt wahrscheinlich die letztere, dh die Laufzeitkosten für die Fakultätsfunktion Berechnung .

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top