如何计算该算法的时间复杂度

Question

我写了一个函数，它获取给定的数字并将其添加到它的反向，直到数字是回文。我正在尝试计算我的代码的时间复杂度，但我根本不知道如何去做，甚至不知道如何开始。有人可以告诉我该怎么做吗？另外，这是最有效的方法还是将整数转换为字符串更好？

void getPali(int num) {        
    int n = 0;
    int nNum;
    while(true) {
        nNum = num;
        int rNum = 0;            
        while (nNum > 0) {
            int rem = nNum % 10;                
            nNum = nNum / 10;                 
            rNum = rNum * 10 + rem;                
        }
        if(rNum == num) break;
        num += rNum;              
        n++;
    }
}

Answer 1

嗯，作为输入值 num 的函数。此代码块：

while (nNum > 0) {
    int rem = nNum % 10;                
    nNum = nNum / 10;                 
    rNum = rNum * 10 + rem;                
}

将不得不执行 log(n) 次。这是因为每次通过此循环都会将 nNum 减少 10 倍。因此对于 2^10 的数字，将需要 10 次循环迭代才能完成。此外，因为在每个循环开始时 nNum 被重置为 n，所以这个循环每次运行将花费相同的时间。

那么循环的下一部分是

if(rNum == num) break;
num += rNum;              
n++;

这本质上是循环条件，但它的写法很奇怪。较大的循环将执行到 rNum = num。所以问题是 rNum 增加的速度有多快。答案是rNum每经过一个大循环就会增加10倍，因此要达到num，又需要lg(n)的时间。

所以综合时间复杂度是log(n)^2。因为外循环执行了log(n)次，内循环执行了log(n)次。因此时间复杂度是log(n)^2 (or log^2(n))

Answer 2

是否存在以10为底数的Lychrel numbers是数学上的未解题。Lychrel数是指反复将一个数取反并自加而不能产生回文的数。

由于您的代码实现了这个过程，因此无法说明您的代码的时间复杂度。

当然，这假设 "int" 是无界的，并且不会像在真正的 java 程序中那样环绕，但无论如何时间复杂度对于有界域来说是没有意义的。

起点196推测不终止

如何计算该算法的时间复杂度

How to calculate time complexity for this algorithm

java

algorithm

time-complexity