对数函数的复杂度是什么？

Question

以10为底的对数函数的复杂度是什么？

- Paul Manta

---

这不取决于所使用的算法吗？例如，查找表是O(1)。 - Thilo

Answer 1

这取决于你想计算对数的值所在的域。

对于IEEE双精度浮点数，许多处理器可以在单个汇编指令中进行对数运算；例如x86有FYL2X和FYL2XP1指令。尽管通常这些指令只能采用某个固定底数的对数，但是它们可以通过使用以下事实来用于任意底数的对数计算：

log_a b = log_c b / log_c a

只需取两个对数并找到它们的商即可。

对于一般整数（任意精度），您可以使用重复平方结合二分搜索以仅使用O（log log n）算术操作进行对数运算（每次平方一个数时，指数翻倍，这意味着您只能将该数字平方log log n次，然后就超过了其值，可以进行二分搜索）。利用一些有趣的Fibonacci数学技巧，您可以仅使用O（log n）空间完成此操作。如果您正在计算二进制对数，则可以使用位移的巧妙技巧以更短的时间计算值（尽管渐近复杂度是相同的）。

对于任意实数，逻辑更加复杂。您可以使用牛顿法或泰勒级数来计算某个精度内的对数，但我承认我不熟悉执行此操作的方法。但是，您很少需要这样做，因为大多数实数都是IEEE双精度浮点数，并且在这种情况下有更好的算法（甚至硬件指令）。

希望这有所帮助！

- templatetypedef

---

对于整数，通常也有一条指令（或者一个简短的序列），可以执行CTZ(x & (x - 1))或wordsize - LZC(x)，但据我所知，这并不对时间复杂度有任何帮助（只是实际速度）。 - harold

@templatetypedef 你可以乘以一个常数因子，以获得任何其他底数的对数，就像你刚刚展示的那样。 :) - Nick Johnson

@NickJohnson 是的，虽然它确实很快，但我们应该注意到，乘法运算本身具有高于对数复杂度的特点：https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations - Rustam A.

Answer 2

如何在O(1)的时间复杂度内计算以2为底、指数为n的对数（其中n是整数）

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

关于__builtin_clzl(x)，请参考这里

- iamakshatjain

---

这将计算数字的二进制对数，假设该数字是整数。但是，如果您想计算以10为底数的对数，我认为您需要使用不同的策略。 - templatetypedef

这段代码实际上返回以2为底的对数。 - Abhay Gupta

@iamakshatjain，您可以更新代码，使其适用于用户指定的任何基值。 - taurus05