log base 10函数的复杂度是多少？
问问题
30882 次
2 回答
51
这实际上取决于您要计算对数的值的域。
对于 IEEE 双精度数，许多处理器可以在一条汇编指令中取对数；例如，x86 具有 FYL2X 和 FYL2XP1 指令。尽管通常像这样的指令只会取某个固定底数的对数，但它们可以用于取任意底数的对数，方法是使用以下事实：
日志a b = 日志c b / 日志c a
通过简单地取两个对数并找到它们的商。
对于一般整数（任意精度），您可以使用重复平方和二进制搜索相结合，仅使用 O(log log n) 算术运算来取对数（每次平方一个数字时，您将指数加倍，这意味着您只能平方在您超过其值并且可以进行二进制搜索之前的数字 log log n 次）。使用斐波那契数的一些可爱技巧，您可以在 O(log n) 空间内完成此操作。如果您正在计算二进制对数，则可以使用一些可爱的技巧与位移一起在更短的时间内计算该值（尽管渐近复杂度是相同的）。
对于任意实数，逻辑更难。您可以使用牛顿法或泰勒级数来计算一定精度内的对数，但我承认我不熟悉执行此操作的方法。但是，您实际上很少需要这样做，因为大多数实数都是 IEEE 双精度数，并且在这种情况下有更好的算法（甚至是硬件指令）。
希望这可以帮助！
于 2011-09-06T09:17:08.390 回答
9
要做log(n)in O(1)( 其中n 是一个整数)
int log(long long x)
{
return 64 - __builtin_clzl(x) - 1;
}
__builtin_clzl(x)参考这里_
于 2020-05-15T21:36:14.333 回答