反转N位整数的时间复杂度为何是O(log N)而非O(N)？

先看这段反转整数的Java代码：

public class Main {
   static int reverse(int X) {
      int Y = 0;
      while (X > 0) {
         //Extract the last digit
         int digit = X % 10;
         //Appending last digit
         Y = Y * 10 + digit;
         // Shrinking X by discarding the last digit
         X = X / 10;
      }
      return Y;
   } 
}

核心原因：循环次数取决于输入的位数，而非数值大小 #

• 这段代码的循环逻辑很直接：每次把输入整数X做10进制整数除法（直接丢弃最后一位），直到X变为0时停止循环。比如输入X=12345，循环会执行5次——对应这个数的5位数字，每处理一位就缩短一次X。
• 一个十进制整数N的位数，数学上等于log₁₀(N) + 1（比如12345的log₁₀值约为4.09，加1就是5位）。时间复杂度分析中，常数项和对数的底数可以忽略（不同底数的对数只相差一个固定倍数，不影响量级），所以循环次数的量级是O(log N)，整个代码的时间复杂度自然就是O(log N)。

为什么不是O(N)？ #

O(N)代表循环次数和输入的数值大小线性相关——比如从1遍历到N，循环次数等于N，这才是典型的O(N)复杂度。但在这段代码里，哪怕输入的N从100涨到1000000，循环次数只是从3次涨到7次，增长速度远慢于N本身，完全不符合线性增长的特征，因此不可能是O(N)。

内容的提问来源于stack exchange，提问作者The Droid Guy