运行 我的 Collat​​z (3n+1) 算法的时间

Question

所以我想弄清楚我算法的运行时间是多少

    #include <iostream>
    using namespace std;
    int steps = 0;

    void collatz(int n)
    {
        if(n % 2 == 0)
        {
            n = n/2;
            steps++;
        }
        else
        {
            n = 3*n + 1;
            steps++;
        }

        if(n==1)
        {
            return;
        }
        else
        { 
            collatz(n);
        }
    }

    int main () 
    {
        int x = 0;
        int *L = new int[x];

        cout << "Hello world " << endl; 

        for(int n = 1;n <= 27;n++)
        {
            collatz(n);
            L[x] = steps;
            x++;
            steps = 0;
        } 

        cout << "|";
        for(int i = 0;i < x;i++)
        {
            cout <<  L[i] << "|";
        }
        cout << endl;
        return 0;
    }

所以基本上我有一个 for 循环迭代 n 次 O(n) 并且对于每个 n 我调用 collat​​z 函数，这是一个递归函数。我们可以说 T(n) = 3n+1 如果 n 是奇数并且 T(n) = n/2 of n 是偶数我们可以考虑 3n+1 因为它大于 n/2 但是然后 T( n)= 3n+1 然后呢？

Answer 1

我认为没有人知道答案。实际上，您的程序甚至可能永远不会终止，因为从未证明 n 将始终达到值 1，尽管人们相信它确实如此（这就是 Collatz conjecture）

Answer 2

John Horton Conway 在 1972 年证明了 Collat​​z 问题的自然推广在算法上是不可判定的，因此您的函数不可能有界（目前）。