我只是增加了反转数字的复杂性吗？

Question

public class HelloWorld{

 public static void main(String []args){

    int  orig=103, reverse=0, mod;
    int numOfDigits=0;
    int n = orig;

    while (n>0){
        n /= 10;
        numOfDigits++;
    }
    n = orig;
    while (n > 0){
        mod = n % 10;
        reverse = reverse + (int)(mod * java.lang.Math.pow(10, numOfDigits-1));
        numOfDigits--;
        n /= 10;
    }

System.out.println("Reversed is : " + reverse);
 }

}

我知道 reverse = reverse + (int)(mod * java.lang.Math.pow(10, numOfDigits-1)); 可以用 reverse = mod + (reverse*10) 代替。

想知道我是否只是通过计算总位数和应用幂来增加简单程序的复杂性？

P.S：请假设 orig 可以作为用户的输入，并且可以是任意数量的数字。我硬编码只是为了实验。

Answer 1

计算乘法和加法次数：
假设 f(x) = an * x^n + an-1 * x^n-1 + ... + a1 * x + a0
1.如果通过一项一项计算计算f(x)，
需要 (n+1) + n + (n-1) + ... + 1 + 0 = (n+1)(n+2)/2 次乘法和 n 次加法。
2.如果通过n = n*10 + mod,
计算f(x) 需要 n 次乘法和 n 次加法。

当然如果pow()有一些优化比如"divide and conquer"，pow()的复杂度应该是O(logN)。

Answer 2

您没有增加复杂性……但确实使它变慢了。表达式 pow(10, numOfDigits - 1) 将比 reverse = mod + (reverse * 10)

慢得多

^{使用 Math.pow 而不是整数乘法的计算也可能由于浮点不精确而不准确。 double 只有 52 位精度，而 long 有 63 位精度。在这个例子中，这可能不适用，但它是需要警惕的，一般来说}

Answer 3

可能，这将是 较少迭代 和 复杂性 的最佳方法：

public class NumReverse {

public long reverseNumber(long number){

    long reverse = 0;
    while(number != 0){
        reverse = (reverse*10)+(number%10);
        number = number/10;
    } 
    return reverse;
}

public static void main(String a[]){
    System.out.println("Reversed is: "+new NumReverse().reverseNumber(103));
}
}

我只是增加了反转数字的复杂性吗？

Did I just increase the complexity of reversing a number?

java

algorithm

reverse