Komplexität faktorieller rekursiven Algorithmus

Question

heute in der Klasse mein Lehrer schrieb an die Tafel dieses rekursiven faktorielles Algorithmus:

int factorial(int n) { 
    if (n == 1) 
     return 1; 
    else 
     return n * factorial(n-1); 
} 

Sie sagte, dass es eine Gebühr von T(n-1) + 1 hat.

Dann mit der Iterationsmethode sagte sie, dass T(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j, so dass der Algorithmus stoppt, wenn n - j = 1, also j = n - 1.

Danach ersetzte sie j in T(n-1) + 1 und erhielt T(1) + n-1.

Sie sagte direkt die für diese n-1 = 2 ^{(log n-1)}, so dass die Kosten des Algorithmus ist exponentiell.

Ich habe wirklich die letzten zwei Schritte verloren. Kann mir bitte jemand erklären?

Answer 1

Beginnen wir mit der Analyse dieses Algorithmus. Wir können eine Wiederholungsbeziehung für den Gesamtbetrag der geleisteten Arbeit schreiben. Als Basisfall, haben Sie eine Arbeitseinheit, wenn der Algorithmus auf einem Eingang der Größe 1 ausgeführt wird, so

T (1) = 1

für eine Eingabe von Größe n + 1 , Ihr Algorithmus führt innerhalb der Funktion eine Arbeitseinheit aus und ruft dann bei einer Eingabe der Größe n dieselbe Funktion auf. Daher

T (n + 1) = T (n) + 1

Wenn Sie die Bedingungen der Wiederholung erweitern aus, Sie bekommen, dass

• T (1) = 1
• T (2) = T (1) + 1 = 2
• T (3) = T (2) + 1 = 3
• T (4) = T (3) + 1 = 4
• ...
• T (n) = n

Also dieser Algorithmus in der Regel erfordert n Einheiten der Arbeit zu vollenden (d T (n) = n).

Das nächste, was Ihr Lehrer sagte, war, dass

T (n) = n = 2 ^{log n}

Diese Aussage wahr ist, weil 2 ^{log x} = x für alle Werte ungleich Null, da Potenzierung und Logarithmen inverse Operationen voneinander sind.

Die Frage ist also: ist das Polynom Zeit oder exponentielle Zeit? Ich würde dies als Pseudopolynomialzeit einstufen.Wenn Sie die Eingabe x als Zahl behandeln, ist die Laufzeit tatsächlich ein Polynom in x. Die Polynomzeit ist jedoch formal so definiert, dass die Laufzeit des Algorithmus ein Polynom in Bezug auf die Anzahl der Bits sein muss, die verwendet werden, um die Eingabe für das Problem zu spezifizieren. Hier kann die Zahl x nur in Θ (log x) Bits angegeben werden, so dass die Laufzeit von 2 ^{log x} technisch als exponentielle Zeit betrachtet wird. Ich habe darüber als Länge in this earlier answer geschrieben, und ich würde empfehlen, es für eine gründlichere Erklärung zu suchen.

Hoffe, das hilft!