低于O(log )和非O(n)的复杂度如何？
低于O(log )和非O(n)的复杂度如何？
提问于 2018-09-11 01:24:08
有人能解释一下为什么这个算法是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;
}回答 1
Stack Overflow用户
发布于 2018-09-11 03:13:29
这取决于n是什么。如果n本身是一个数值x，那么复杂度就是O(log(n))。如果将x乘以10，则while循环只会增加一次迭代时间，而不是十倍。同样，将x乘以100只会增加两次迭代。
另一方面，如果有一个变量s，它是x的字符串表示，n是字符串s的长度，那么复杂度将是O(n)。请注意，在这种情况下，s的长度与log(x)成正比，因此从数值的角度来看，对数是隐式的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52262678
复制相关文章
相似问题