Wie lange läuft die Collatz-Rekursion?

Ich habe den folgenden Python-Code.

def collatz(n):
    if n <= 1:
        return True
    elif (n%2==0):
        return collatz(n/2)
    else:
        return collatz(3*n+1)

Wie ist die Laufzeit dieses Algorithmus?

Versuchen:

Wenn die Laufzeit der Funktion bezeichnet . Dann denke ich, ich habe { T ( n ) = 1  für  n ≤ 1 T ( n ) = T ( n / 2 )  für  n  gerade T ( n ) = T ( 3 n + 1 )  für  n $T(n)$collatz(n)

Ich denke, wird lg n sein, wenn n gerade ist, aber wie berechnet man die Wiederholung im Allgemeinen?$T(n)$$\lg n$$n$

$\infty$

Sie haben den Code korrekt übersetzt . Es gibt viele Methoden zum Lösen von Wiederholungen .

Es ist jedoch derzeit nicht bekannt, ob collatzüberhaupt für alle Halt gemacht wird n. die Behauptung, die dies tut, ist als Collatz-Vermutung bekannt . Daher funktioniert keine bekannte Methode bei dieser Wiederholung.

$T(n)$$\lg n$$n$

$n=2^k$$\Theta$

Die Zeitkomplexitätsfunktion ist

Dies kann wie folgt umgeschrieben werden, wenn Sie an asymptotischer Zeitkomplexität interessiert sind.

$\langle M,1^n\rangle \in Halt$$n$$n$

Collatz-Vermutung ist eine sehr berühmte Vermutung, die Collatz 1937 vorschlug. Viele bedeutende Mathematiker haben unzählige Stunden damit verbracht, diese Vermutung zu lösen, aber ohne Erfolg. Sogar Paul Erdős sagte über die Collatz-Vermutung: "Die Mathematik ist für solche Probleme noch nicht bereit."

$n$$odd$$n$$3n+1$

$T(n) = 2T(n/2) +n$$T(0)$$T(1)$

$3n+1$

Sie haben T (n) = T (n / 2) + 1, wenn n gerade ist. Aber dann n / 2 ist ziemlich wahrscheinlich nicht einmal, so dass Sie dort festsitzen.

Was passiert ist, dass die netten kleinen Regeln, die Sie gelernt haben, mit einem echten Problem konfrontiert sind und nicht funktionieren. Sie schlagen mit dem Gesicht voran gegen eine Mauer und es tut weh. Tun Sie sich selbst einen Gefallen, und folgen Sie der Rekursion für T (7) manuell. Dann erfahren Sie, ob Sie immer noch der Meinung sind, dass dies mit lg n zusammenhängt.

Wenn Sie glauben, dass dies nicht mit der ursprünglichen Frage zusammenhängt, weil 7 nicht gerade ist: Immer wenn n ungerade ist, ist T (n) = T (3n + 1) und 3n + 1 gerade. Wenn also T (n) logarithmisch wäre n wenn n gerade ist, wäre es log (3n + 1) + 1, wenn n> 1 ungerade ist.