У меня есть следующий код Python.
def collatz(n):
if n <= 1:
return True
elif (n%2==0):
return collatz(n/2)
else:
return collatz(3*n+1)
Каково время работы этого алгоритма?
Пытаться:
Если обозначает время работы функции . Тогда я думаю, что у меня
{ T ( n ) = 1 для n ≤ 1 T ( n ) = T ( n / 2 ) для n четных T ( n ) = T ( 3 n + 1 ) для n нечетныхcollatz(n)
Я думаю, что будет если четное, но как рассчитать повторение в целом?lg n n
collatz
тег на MathOverflow и т. д. последние исследования показывают, что проблема имеет внутренние фрактальные качества, что усложняет задачу.Ответы:
Это гипотеза Коллатца - все еще открытая проблема.∞
Гипотеза о доказательстве того, что эта последовательность останавливается для любого ввода, поскольку это не разрешено, мы не знаем, как решить это отношение повторения во время выполнения, более того, оно может вообще не останавливаться - поэтому, пока не доказано, время выполнения неизвестно и может быть .
источник
Вы правильно перевели код . Есть много методов для решения рецидивов .
Тем не менее, в настоящее время неизвестно,
collatz
остановится ли вообще для всехn
; утверждение, что это так, известно как гипотеза Коллатца . Таким образом, ни один из известных методов не будет работать в этом случае.источник
Функция временной сложности
который можно переписать следующим образом, если вас интересует асимптотическая сложность времени.
Гипотеза Коллатца - очень известная гипотеза, предложенная Коллатцем в 1937 году. Многие выдающиеся математики потратили (читай впустую) бесчисленные часы, пытаясь разгадать эту гипотезу, но безрезультатно. Даже Пол Эрдос сказал о гипотезе Коллатца: «Математика еще не готова к таким проблемам».
источник
источник
У вас есть T (n) = T (n / 2) + 1, если n четно. Но тогда n / 2, скорее всего, даже не очень, так что вы застряли там.
Происходит то, что милые маленькие правила, которые вы выучили, сталкиваются с реальной проблемой, и они не работают. Они бьют по кирпичной стене лицом в первую очередь, и это больно. Сделайте себе одолжение и выполните рекурсию для T (7) вручную, и тогда вы скажете, все еще ли вы считаете, что это связано с lg n.
Если вы думаете, что это не связано с исходным вопросом, потому что 7 не четное: всякий раз, когда n нечетно, T (n) = T (3n + 1), а 3n + 1 четно, поэтому, если T (n) были записаны n, если n четное, то будет log (3n + 1) + 1 всякий раз, когда n> 1 нечетно.
источник