对数函数的复杂度是多少？
以 10 为底的对数函数的复杂度是多少？
What is the complexity of the log base 10 function?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
以 10 为底的对数函数的复杂度是多少？
What is the complexity of the log base 10 function?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（2）
在
O(1)（其中 n 是整数）中对
__builtin_clzl(x)执行log(n)> 请参阅此处To do
log(n)inO(1)( where n is an integer )for
__builtin_clzl(x)refer here这实际上取决于您想要计算对数的值的域。
对于 IEEE 双精度数，许多处理器可以在单个汇编指令中取对数；例如，x86 具有 FYL2X 和 FYL2XP1 指令。虽然像这样的指令通常只会取某个固定底数的对数，但它们可以通过以下事实用于取任意底数的对数：
只需取两个对数并找到它们的商即可。
对于一般整数（任意精度），您可以使用重复平方结合二分搜索来仅使用 O(log log n) 算术运算来取对数（每次对数字进行平方时，指数都会加倍，这意味着您只能平方在超过其值并可以进行二分搜索之前，数字 log log n 次）。使用一些斐波那契数列的可爱技巧，您只需 O( log n) 空间。如果您正在计算二进制对数，您可以使用 bit 来使用一些可爱的技巧转变以在更短的时间内计算值（尽管渐近复杂度是相同的）。
对于任意实数，逻辑更加困难。您可以使用牛顿法或泰勒级数来计算一定精度内的对数，尽管我承认我不熟悉执行此操作的方法。然而，您实际上很少需要这样做，因为大多数实数都是 IEEE 双精度数，并且在这种情况下有更好的算法（甚至硬件指令）。
希望这有帮助！
This really depends on the domain of what values you want to compute a logarithm of.
For IEEE doubles, many processors can take logarithms in a single assembly instruction; x86 has the FYL2X and FYL2XP1 instructions, for example. Although typically instructions like these will only take the logarithm in some fixed base, they can be used to take logarithms in arbitrary bases by using the fact that
by simply taking two logarithms and finding their quotient.
For general integers (of arbitrary precision), you can use repeated squaring combined with a binary search to take logarithms using only O(log log n) arithmetic operations (each time you square a number you double the exponent, which means you can only square the number log log n times before you've exceeded its value and can do a binary search). Using some cute tricks with Fibonacci numbers, you can do this in only O(log n) space. If you're computing the binary logarithm, there are some cute tricks you can use with bit shifts to compute the value in less time (though the asymptotic complexity is the same).
For arbitrary real numbers the logic is harder. You can use Newton's method or the Taylor series to compute logarithms to within a certain precision, though I confess that I'm not familiar with the methods for doing this. However, you rarely actually need to do this because most real numbers are IEEE doubles and there are better algorithms (or even hardware instructions) in that case.
Hope this helps!