To jest problem z mojego podręcznika. TheHipoteza Collatza (lub problem „3n + 1”) działa w następujący sposób (podając pewną liczbę naturalnąn):

while n > 1 do
    if n is even then
        n = n / 2
    else
        n = 3n + 1
    end if
end while

Przejrzałem kilka artykułów na temat przypuszczeń, ale wszystkie przeszły mi przez głowę. Próbuję uzyskać podstawową wiedzę na temat złożoności algorytmu. Czy można skomentować górną lub dolną granicę liczby wykonanych operacji (w najgorszym przypadku)?

Jedyną rzeczą, jaką udało mi się wywnioskować, jest to, że wejście najlepszego przypadku musi mieć postać n = 2 ^ k (co spowoduje najmniejszą liczbę operacji). Czy można powiedzieć, że najgorszym przypadkiem jest brak mocy dwóch?

Walczyłem z próbą konceptualizacji szorstkiej górnej lub dolnej granicy. Dla każdegon, wydaje się, że jest zbyt dużo przełączania z nieparzystego na parzyste (co powoduje wzrost o współczynnik 3 lub zmniejszenie o współczynnik 2), aby skomentować najmniej / największą ilość wykonanych obliczeń.

Każda pomoc jest doceniana.