運行我在Collat​​z的時間（3N + 1）算法

Question

所以我想弄清楚什麼是我的算法的for循環迭代n中的運行時間

#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; 
    } 

所以基本上我有一個時間爲O（n）對於每個n我稱之爲遞歸函數collat​​z函數。我們可以說如果n是奇數並且n的T（n）= n/2是偶數，T（n）= 3n + 1，我們可以考慮3n + 1，因爲它大於n/2，但是然後T（n）= 3n +1然後呢？

Answer 1

我不認爲有人知道答案。其實，你的程序甚至可能永遠不會終止，因爲它從來沒有被證明，n總會達到價值1，g雖然人們認爲它（這是Collatz conjecture）

Answer 2

約翰·霍頓康威在1972年證明了自然Collat​​z問題的推廣在算法上是不可判定的，所以你的函數（現在）沒有可能的邊界。