日志功能的复杂性是多少？

Question

日志库10功能的复杂性是多少？

Answer 1

这实际上取决于您想要计算对数的值的域.

对于IEEE双精度,许多处理器可以在单个汇编指令中取对数; 例如,x86具有FYL2X和FYL2XP1指令.虽然通常这样的指令只会在某个固定基数中取对数,但它们可以用于通过使用以下事实在任意基数中取对数.

log _a b = log _c b/log _c a

通过简单地取两个对数并找到它们的商.

对于一般整数(任意精度),您可以使用重复平方结合二分搜索来仅使用O(log log n)算术运算来取对数(每次将数字加倍,使指数加倍,这意味着您只能对数字日志记录在超过其值之前n次,并且可以进行二进制搜索.使用斐波那契数字的一些可爱技巧,你可以只在O(log n)空间中执行此操作.如果你正在计算二进制对数,你可以使用一些可爱的技巧来进行位移以在更短的时间内计算值(尽管渐近复杂度是相同的).

对于任意实数,逻辑更难.您可以使用牛顿方法或泰勒级数来计算一定精度内的对数,但我承认我不熟悉这样做的方法.但是,您实际上很少需要这样做,因为大多数实数都是IEEE双精度数,并且在这种情况下有更好的算法(甚至是硬件指令).

希望这可以帮助!

Answer 2

要做到log(n)在O(1)（其中n为整数）

int log(long long x)
{
    return 64 - __builtin_clzl(x) - 1;
}

为__builtin_clzl(x)参照这里