java - 反向然后添加序列 : Big-O runtime of my solution?

Question

首先，这不是作业:我在 CodeEval 上提交了一些 Java 代码。

挑战归结为以下问题:

Start with a number n. If it's a palindrome, stop. Otherwise, reverse the digits of n, add them to n, and repeat this process. Report how many steps are necessary before the number converges to a palindrome.

一点都不难。此外，在我提交代码并获得 100% 的挑战后，我开始再次查看我的代码 - 我想确定我的递归调用方法的时间复杂度以及在递归方法中调用我的方法。

其中，我想到了:

//adds the i'th integer in String[] data to its reversed integer:
private final int add(int x)
{
    //if x is 0, then don't do anymore computation
    if(x==0)
    {
        count++;   
        return x;
    }
    //if x equals its reversal, the palindrome has been found
    if(x==rev(x))
    {
      return x;
    }

    //keep adding and reversing
    else
    {
        //if MAX has been reached, STOP
         if (count==MAX)
         return 0;

         //increment the count
         count++;
        _intTmp=rev(x); //get the reversal 

        return add(x + _intTmp); //recursive call: keep adding
    }//else:end
} //Main::add() end

所以...我计算了 T(N): 1 + log(1/n)

//reverse the integer: worst case is O(N)
private final int rev(int orig) 
{
    int reversed=0;
    while(orig>0)
    {
        //adds the last digit from orig to reversed
        reversed=reversed*10+orig%10; 
        orig=orig/10; //gets rid of the last digit    
    }
    return reversed; //return the reversed integer  
}//Main::final end

我计算了:O(N)

此代码片段的总体时间复杂度为:O(1+log(1/n)+n) ~ O(N)

我是对的，还是我哪里搞砸了？

感谢您的宝贵时间和建议...

Answer 1

我认为没有人知道这个函数的大 O 运行时是什么，或者它是否有大 O 运行时。挑战暗示某些数字最终是否以这种方式形成回文是未知的。事实上，这是数学中的一个悬而未决的问题；这样的数字称为 Lychrel number没有人知道它们是否存在!

如果存在多个这种形式，您的算法在其上运行时将进入无限循环，因此该输入的运行时间将没有上限。另一方面，如果不存在这种形式的数字，则运行时限制将取决于您必须将数字的倒数与其自身相加以形成回文的总次数。

但是，现在，让我们假设所需的迭代次数是有限的。假设对于任何数字 n，都有一个数字 f(n) 告诉您必须使用数字反转和相加技巧的次数。请注意，每次反转数字并相加时，数字最多增加 9 倍。添加 d 位数字需要时间 O(d)，反转 d 位数字也需要时间 O(d)。另外，请注意数字 n 中有 O(log n) 位数字。因此，运行时将是

log n + 9 log n + 9² log n + ... + 9^f(n) log n

= O(9^f(n) log n)

因此，如果确实存在必要步骤数的上限 f(n)，则运行时间将为 O(9^f(n) log n)。

我不确定您如何将 O(1 + 1/log n) 作为主要步骤的运行时间。如果您提供更多有关您如何得出这一点的详细信息，我可以尝试帮助您更详细地检查您的逻辑。

希望这对您有所帮助!