为什么这个求逆整数（Leet 代码）的解是 O((log10(n))？

Question

有问题的 problem 要求反转 32 位有符号整数。这是 Java 中给出的解决方案：

    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

根据解法的解释，时间复杂度为O(log10(n))，因为x中大概有log10(x)个数字。直观上，while 循环似乎有 n-1 次迭代，其中 n 是位数。（即：一个 7 位数需要 6 次迭代）但是，解决方案和给定的复杂性意味着 n 是整数本身而不是位数。任何人都可以帮助我直观地理解为什么上述解决方案是 log10(n) 吗？

Answer 1

Let's say the x = 123.

int rev = 0;

rev = rev * 10 + x % 10; // rev = 3,   1st iteration.

x = x/10;              // x = 12

rev = rev * 10 + x % 10;  // rev = 3 * 10 + 2 = 32,  2nd iteration

x = x/10;              // x = 1

rev = rev * 10 + x % 10;  // rev = 32 * 10 + 1 = 321, 3rd iteration.

x = 0 so the  loop terminates after 3 iterations for 3 digits.

循环中的条件检查反转值是否会超过 32 位数字所能容纳的值。

因此 log10(n) 正是您在问题中陈述的原因。给定基数 n 的对数是将 base 提升回数字 n 所需的 exponent。指数是数字中 number of digits 的近似值。

根据您的评论，也可以说 "For any number n, where m is the the number of digits in n, the time complexity is O(m)."

Answer 2

如果x是整数，则floor(log10(x)) + 1等于x的位数。

设 log(10)x = 某个数字 y。然后 10^y = x.
例如，

log(10) 10 = 1   
log(10) 100 = 2  
log(10) 1000 = 3 
...

当 x 不是 10 的完美幂时：

floor( log(213) ) = 2

如果这不能回答您的问题，请告诉我。

Answer 3

给定的反向算法在最坏的情况下需要 log_10(x) 次迭代。换句话说，如果给定的输入 x 由 k 个十进制数字组成，则需要 k 次迭代。但是说这个算法是 O(log_10(x)) 是误导。这不是对数算法。如果输入大小不直观（例如，测试给定整数是否为素数），我们需要严格应用输入大小的正确定义。在 Big O 分析中，输入大小定义为写入输入所需的字符数。由于我们通常将整数编码为二进制数字，因此该算法 n 的输入大小约为 log_2 x。因此，x 大约为 2^n。最坏情况复杂度 W(x) = log_10 (x) = log_10(2^n) = n log_10(2)。所以逆向算法的大O是O(n).

为什么这个求逆整数（Leet 代码）的解是 O((log10(n))？

Why is this solution to Reverse Integer (Leet Code) O((log10(n))?

java

big-o

logarithm