如何复杂度低于O（log n）而不是O（n）

Question

有人可以解释这个算法是如何O(log(n))而不是O(n)？

循环运行给定数字中的所有数字。所以不是复杂的O(n)？

 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;
}

Answer 1

这取决于n是什么。如果n本身是x，一个数值，那么复杂性就是O(log(n))。如果将x乘以10，则while循环只会延长一次，而不是十倍。同样，将x乘以100只会增加两次迭代。

另一方面，如果有一个变量s，它是x的字符串表示，而n是字符串s的长度，那么复杂性将是O(n)。注意，在这种情况下，s的长度与log(x)成比例，因此从数值的角度来看，对数是隐含的。

Answer 2

这是一个思想实验：

1. 该算法取决于n中的位数，而不是n的值。 n = 10采用与n = 99一样多的迭代，因为它们都有2位数。
2. n中的数字位数以log(n)速率增长，因为添加一个数字需要n至少大10倍。

因此，该算法具有O(log(n))的复杂性