¿Cuánto dura la recursión de Collatz?

19

Tengo el siguiente código de Python.

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

¿Cuál es el tiempo de ejecución de este algoritmo?

Tratar:

Si denota el tiempo de ejecución de la función . Entonces creo que tengo $T(n)$ collatz(n)

{\begin{cases} T (n) = 1 for n \leq 1 \\ T (n) = T (n / 2) for n even \\ T (n) = T (3 n + 1) for n odd \end{cases}

$\begin{cases} T(n)=1 \text{ for } n\le 1\\ T(n)=T(n/2) \text{ for } n\text{ even}\\ T(n)=T(3n+1) \text{ for } n\text{ odd}\\ \end{cases}$

Creo que será si es par, pero ¿cómo calcular la recurrencia en general? $T(n)$ $\lg n$ $n$

algorithm-analysis runtime-analysis recurrence-relation 9bi7
fuente

44

Eso debería ser y así sucesivamente. El +1 es importante, de lo contrario tiene , para todos los para los que termina la secuencia.

T (n) = T (\frac{n}{2}) + 1

$T(n) = T(\frac n2) + 1$

T (n) = 1

$T(n) = 1$

n

$n$

user253751

2

54 es par, T (54) = 112! = Lg (54)

Taemyr

¿Se supone que el usuario solo ingresará un entero?

Dean MacGregor

@DeanMacGregor Sí. De hecho, se supone un número entero positivo .

duskwuff

más detalles de bkg serían útiles. ¿de dónde sacaste el código, cómo te lo presentaron? Este es un problema abierto semifamoso en la teoría de números sin resolver durante ~ ¾ siglo en el que se ha escrito un libro entero de Lagarias. de CS pov demostrando que está en cualquier clase de complejidad de tiempo o espacio es equivalente a una prueba. Muchas más referencias aquí . También es un gran tema para Computer Science Chat para cualquier persona interesada. También hay una collatzetiqueta en MathOverflow, etc. Las últimas investigaciones muestran que el problema tiene cualidades fractales intrínsecas que lo dificultan.

vzn

29

Esta es la conjetura de Collatz, un problema aún abierto.
La conjetura es sobre la prueba de que esta secuencia se detiene para cualquier entrada, ya que esto no está resuelto, no sabemos cómo resolver esta relación de recurrencia en tiempo de ejecución, además, es posible que no se detenga en absoluto, por lo que hasta que se pruebe, el tiempo de ejecución es desconocido y puede ser . $\infty$

Mal
fuente

Gracias. Pero mi recursión es verdadera ¿verdad? Si es así, ¿aún no podemos encontrar la solución para esa recursión?

9bi7

¿Qué quieres decir con "la recursividad es verdadera"? No puede encontrar el tiempo de ejecución, pero para muchos números esto hará algunos saltos y llegará a 1.

no denota el tiempo de ejecución sino la función en sí.

T (n)

$T(n)$

Evil

Por correcto quería decir, por ejemplo, como en el orden de combinación podemos obtener

. Dado que el código es recursivo, podemos escribir la recurrencia para él, ¿verdad?

T (n) = 2 T (n / 2) + O (n)

$T(n)=2T(n/2)+O(n)$

9bi7

77

"Dado que esto no está resuelto, no hay límite superior", tenemos que tener cuidado con el lenguaje aquí. No sabemos la solución de esta recurrencia, final de la historia.

Raphael

77

Si. Pero "no sabemos" no es lo mismo que "no hay límite superior". Básicamente, estoy dividiendo pelos sobre matemáticos "hay" (

) y personas normales "hay" ("tengo uno"). Sin embargo, creo que esta es una distinción importante que se debe hacer en TCS .

\exists

$\exists$

Raphael

15

Has traducido el código correctamente . Existen muchos métodos para resolver las recurrencias .

Sin embargo, actualmente se desconoce si collatzincluso se detiene para todos n; la afirmación de que sí se conoce como conjetura de Collatz . Por lo tanto, ningún método conocido funcionará en esta recurrencia.

Creo que será si es par $T(n)$ $\lg n$ $n$

¿Cómo es eso? Supongo que estás pensando en , para lo cual tu afirmación es correcta. Esto demuestra que esta recurrencia no es una que podamos resolver hasta investigando exponencialmente pocos puntos (ver también aquí ). $n=2^k$ $\Theta$

Rafael
fuente

13

La función de complejidad temporal es

{\begin{cases} T (n) = O (1) for n \leq 1 \\ T (n) = T (n / 2) + O (1) for n even \\ T (n) = T (3 n + 1) + O (1) for n odd \end{cases}

$\begin{cases} T(n)= O(1) \text{ for } n\le 1\\ T(n)=T(n/2) + O(1) \text{ for } n\text{ even}\\ T(n)=T(3n+1) + O(1)\text{ for } n\text{ odd}\\ \end{cases}$

que puede reescribirse como sigue si está interesado en la complejidad asintótica del tiempo.

{\begin{cases} T (n) = 1 for n \leq 1 \\ T (n) = T (n / 2) + 1 for n even \\ T (n) = T (3 n + 1) + 1 for n odd \end{cases}

$\begin{cases} T(n)= 1 \text{ for } n\le 1\\ T(n)=T(n/2) + 1 \text{ for } n\text{ even}\\ T(n)=T(3n+1) + 1\text{ for } n\text{ odd}\\ \end{cases}$

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

La conjetura de Collatz es una conjetura muy famosa que Collatz propuso en 1937. Muchos matemáticos eminentes han pasado (leído perdido) innumerables horas tratando de resolver esta conjetura, pero fueron en vano. Incluso Paul Erdős dijo sobre la conjetura de Collatz: "Las matemáticas aún no están listas para tales problemas".

Shreesh
fuente

1

"desperdiciado" es un juicio subjetivo. vea el análisis experto de Lagarias para conocer las razones por las cuales el trabajo / resultados parciales en la conjetura pueden considerarse como "no desperdiciados". También la cita de Erdos es probable que tenga algunas décadas y las matemáticas han progresado sustancialmente desde entonces, y continúa ... y probablemente no se han intentado todas las nuevas técnicas matemáticas contra el problema.

vzn

Ese fue un comentario irónico. (Para ser justos, lo puse entre paréntesis, ¿no?). Hasta que se resuelva el problema, todos los esfuerzos parecen ser un desperdicio, pero una vez que se resuelve, se ve cómo incluso las fallas han llevado a la solución. Y no estoy de acuerdo con ustedes en que las matemáticas han progresado sustancialmente; la tecnología ha progresado sustancialmente, pero la física, las matemáticas e incluso la informática están progresando lentamente, y así es como debería ser (puedo decir esto porque, yo que aprendí mis cuerdas hace 30 años, todavía no me siento anticuado).

Shreesh

3 x + 1

$3x+1$

Lagarias escribió / compiló / editó un libro completo sobre el tema y suena "disculpándose" por estudiar el problema. jajaja todo lo contrario . Sin embargo, estuvo de acuerdo / admitió que tiene una posición defensiva porque muchos otros matemáticos no consideran que el problema sea significativo o que valga la pena un gran ataque / esfuerzo (¡y tenga en cuenta que Gauss sintió exactamente lo mismo sobre Fermats Last Thm!). pero hay otros casos masivos de matemáticos importantes que lo toman totalmente en serio, por ejemplo, Tao .

vzn

2

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

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

$3n+1$

Sorrop
fuente

0

Tienes T (n) = T (n / 2) + 1 si n es par. Pero entonces es muy probable que n / 2 ni siquiera, así que estás atrapado allí.

Lo que sucede es que las pequeñas reglas que aprendiste se enfrentan a un problema real y no funcionan. Golpean una pared de ladrillos, se enfrentan primero, y duele. Hágase un favor y siga la recursividad de T (7) manualmente, y luego le dice si todavía cree que esto está relacionado lg n.

Si cree que esto no está relacionado con la pregunta original porque 7 no es par: siempre que n sea impar, T (n) = T (3n + 1) y 3n + 1 es par, entonces si T (n) fuera log n si n es par, sería log (3n + 1) + 1 siempre que n> 1 sea impar.

gnasher729
fuente

¿Cuánto dura la recursión de Collatz?

Respuestas: