これは私の教科書の問題です。コラッツ予想(または "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 の形式でなければならないということです (これにより、ops が最も少なくなります)。このことから、最悪の場合の入力は 2 の累乗ではないと言っても過言ではありませんか?
大まかな上限または下限を概念化するのに苦労しています。任意のnについて、実行された計算の最小/最大量についてコメントするには、奇数から偶数への切り替えが多すぎるようです (3 倍に増加するか、2 倍に減少します)。
どんな助けでも大歓迎です。