algorithm - Collat​​z猜想:上下限是否宽松？

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗？Update the question所以堆栈溢出的值小于aa>。
这是我课本上的一个问题on-topic（或“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）。
在所有输入的序列总是终止的情况下，我们必须更仔细地研究为什么会出现这种情况，以便确定“最坏情况”的输入是什么不太可能两种力量的所有非力量都是最坏情况下的投入很有可能会有一个无穷多的自然数族，这些自然数在其大小周围形成数字的最坏情况输入，类似于斐波那契数如何给欧几里得算法提供最坏情况输入。
当然，这些现在都不为人所知——这就是处理开放性问题的好处！
希望这有帮助！

关于algorithm - Collat​​z猜想:上下限是否宽松？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16905529/