这是我课本上的一道题。这科拉茨猜想（或“3n + 1”问题）的工作原理如下（给定一些自然数n):
while n > 1 do
if n is even then
n = n / 2
else
n = 3n + 1
end if
end while
我浏览了几篇关于这个猜想的论文，但它们都超出了我的理解范围。我试图对算法的复杂性有一个基本的了解。是否可以评论执行的操作数量的上限或下限（在最坏的情况下）？
我唯一能够推断出的是，最好情况的输入必须采用 n = 2^k 的形式（这将导致最少的操作）。由此看来，最坏情况的输入是任何非二的幂是否公平？
我一直在努力尝试概念化粗略的上限或下限。对于任何n，似乎有太多从奇数到偶数的切换（这导致增加 3 倍或减少 2 倍），无法评论执行的最少/最多的计算量。
任何帮助表示赞赏。
基于@Kevin 的评论：现在，我们甚至不确定此过程是否会针对所有输入终止。序列很可能总是终止，并且很可能存在序列永远不会终止的输入。
如果序列对于某些输入永远不会终止，那么最坏情况的输入将是序列永远不会停止的任何数字。这不一定与“任何非二的幂”相同，因为我们知道有许多非二的幂序列收敛（例如，15）。
在序列总是针对所有输入终止的情况下，我们必须更仔细地研究为什么会出现这种情况，以便确定“最坏情况”输入是什么。所有非二的幂不太可能都是最坏情况的输入。很可能会有无限个自然数族形成其大小附近的数字的最坏情况输入，类似于斐波那契数如何为欧几里得算法提供最坏情况输入。
当然，目前这些都不为人所知——这就是处理开放问题的美妙之处！
希望这可以帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
