1

这是我教科书中的一个问题。Collat ​​z 猜想（或“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 的形式（这将导致最少的操作）。由此，可以说最坏情况的输入是任何非 2 的幂吗？

我一直在努力尝试将粗略的上限或下限概念化。对于任何n，似乎有太多从奇数到偶数的切换（这导致增加 3 倍或减少 2 倍）来评论执行的最少/最多计算量。

任何帮助表示赞赏。

4

1 回答 1

3

基于@Kevin 的评论：现在，我们甚至不确定这个过程是否会针对所有输入而终止。序列很可能总是终止，并且很可能存在序列永远不会终止的输入。

如果序列对于某些输入永远不会终止，那么最坏情况的输入将是序列永远不会停止的任何数字。这不一定与“任何非二次方”相同，因为我们知道序列收敛的许多非二次方（例如，15）。

在所有输入的序列总是终止的情况下，我们必须更仔细地研究为什么会这样，以确定“最坏情况”的输入是什么。不太可能所有非二次方都是最坏情况的输入。很可能会有一个无限的自然数族，它们形成与其大小相近的数字的最坏情况输入，类似于斐波那契数如何为欧几里得算法提供最坏情况输入。

当然，现在这些都不为人所知——这就是处理开放问题的美妙之处！

希望这可以帮助！

于 2013-06-03T20:58:07.670 回答