Jak długo trwa rekurencja Collatz?

19

Mam następujący kod Python.

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

Jaki jest czas działania tego algorytmu?

Próbować:

Jeśli oznacza czas działania funkcji . Więc myślę, że mam $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}$

Myślę, że będzie jeśli jest parzyste, ale jak ogólnie obliczyć nawrót? $T(n)$ $\lg n$ $n$

algorithm-analysis runtime-analysis recurrence-relation 9bi7
źródło

4

To powinno być

i tak dalej. +1 jest ważne, w przeciwnym razie masz

, dla wszystkich

dla których sekwencja się kończy.

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

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

T (n) = 1

$T(n) = 1$

n

$n$

user253751,

2

54 jest parzysty, T (54) = 112! =

Lg

Czy zakłada się, że użytkownik wprowadzi tylko liczbę całkowitą?

Dean MacGregor,

@DeanMacGregor Tak. W rzeczywistości przyjmuje się dodatnią liczbę całkowitą.

duskwuff

przydałoby się więcej szczegółów bkg. skąd masz kod, jak go wprowadzono? jest to półsławny otwarty problem teorii liczb nierozwiązany przez ~ pół wieku, na którym napisano całą książkę Lagariasa. z CS pov dowodzącego, że jest ona w dowolnej klasie złożoności w czasie lub przestrzeni jest równoważna z dowodem. wiele innych referencji tutaj . również świetny temat na czacie informatyki dla wszystkich zainteresowanych. istnieje także collatzznacznik na MathOverflow itp. Ostatnie badania pokazują, że problem ma wewnętrzne cechy fraktali, co utrudnia.

dniu

29

$\infty$

Zło
źródło

Dzięki. Ale moja rekurencja jest prawdziwa, prawda? Jeśli tak, to nadal nie możemy znaleźć rozwiązania dla tej rekurencji?

9bi7

T (n)

$T(n)$

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

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

7

„ponieważ jest to nierozwiązane, nie ma górnej granicy” - tutaj musimy zachować ostrożność. Nie znamy rozwiązania tego nawrotu, końca historii.

Raphael

7

\exists

$\exists$

15

Ci prawidłowo przetłumaczone kod . Istnieje wiele metod rozwiązywania nawrotów .

Jednak obecnie nie wiadomo, czy w collatzogóle się zatrzymuje n; twierdzenie, że tak jest, jest znane jako hipoteza Collatza . Dlatego żadna znana metoda nie będzie działać na ten nawrót.

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

$n=2^k$ $\Theta$

Raphael
źródło

13

Funkcja złożoności czasowej to

{\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}$

które można przepisać w następujący sposób, jeśli interesuje Cię asymptotyczna złożoność czasu.

{\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$

Hipoteza Collatza jest bardzo znaną hipotezą, którą Collatz zaproponował w 1937 r. Wielu wybitnych matematyków spędzało (czytało zmarnowane) niezliczone godziny na próbach rozwiązania tej hipotezy, ale bezskutecznie. Nawet Paul Erdős powiedział o przypuszczeniu Collatza: „Matematyka nie jest jeszcze gotowa na takie problemy”.

Shreesh
źródło

1

„zmarnowany” jest subiektywnym osądem. zobacz analizę ekspercką Lagarias, aby dowiedzieć się, dlaczego praca / częściowe wyniki przypuszczenia można uznać za „nie zmarnowane”. również cytat Erdosa ma prawdopodobnie kilka dziesięcioleci i od tego czasu matematyka znacznie się rozwinęła i nadal ... i prawdopodobnie nie podjęto prób wszystkich nowych technik matematycznych przeciwko temu problemowi.

vzn

To był język w komentarzu na policzku. (Aby być uczciwym, umieściłem to w nawiasach, prawda). Dopóki problem nie zostanie rozwiązany, wszystkie wysiłki wydają się marnotrawstwem, ale po jego rozwiązaniu widać, że nawet awarie doprowadziły do rozwiązania. I nie zgadzam się z tobą, że matematyka znacznie się rozwinęła; technologia znacznie się rozwinęła, ale fizyka, matematyka, a nawet informatyka postępują powoli i tak właśnie powinno być (mogę to powiedzieć, ponieważ ja, który nauczyłem się swoich lin 30 lat temu, nadal nie czuję się przestarzały).

Shreesh

3 x + 1

$3x+1$

Lagarias napisał / skompilował / zredagował całą książkę na ten temat i brzmi „przepraszająco” na temat studiowania problemu? lol! wręcz przeciwnie . jakkolwiek się zgodził / przyznał, że ma pozycję obronną, ponieważ wielu innych matematyków nie uważa problemu za znaczący lub wart poważnego ataku / wysiłku (i zauważ, że Gauss czuł się dokładnie tak samo w przypadku Fermats Last Thm!). ale istnieją masowe inne przypadki najlepszych matematyków, którzy traktują to całkowicie poważnie, np. Tao .

vzn

2

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

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

$3n+1$

Sorrop
źródło

0

Masz T (n) = T (n / 2) + 1, jeśli n jest parzyste. Ale wtedy n / 2 prawdopodobnie nie jest nawet, więc utkniesz tam.

To, co się dzieje, polega na tym, że te małe, miłe zasady, których się nauczyłeś, stają przed prawdziwym problemem i nie działają. Uderzają w ścianę z cegły, twarzą w twarz, a to boli. Zrób sobie przysługę i ręcznie wykonaj rekurencję dla T (7), a następnie powiesz, czy nadal uważasz, że jest to związane lg n.

Jeśli uważasz, że nie ma to związku z pierwotnym pytaniem, ponieważ 7 nie jest parzyste: ilekroć n jest nieparzyste, T (n) = T (3n + 1), a 3n + 1 jest parzyste, więc jeśli T (n) było log n, jeśli n jest parzyste, będzie to log (3n + 1) + 1, gdy n> 1 jest nieparzysty.

gnasher729
źródło

Jak długo trwa rekurencja Collatz?

Odpowiedzi: