Shi*_*raj -2 algorithm computer-science logarithm time-complexity
在为基数 2 找到 floor(log(x)) 的算法中，计算 floor(log(x)) 的最佳摊销时间复杂度是多少？
tem*_*def 11
有许多不同的算法用于计算对数，每种算法都代表某种不同的权衡。这个答案调查了各种方法和一些涉及的权衡。
计算 ⌊log b n⌋ 的一种简单方法是计算序列 b 0 , b 1 , b 2等，直到我们找到一个大于 n 的值。那时，我们可以停止，并返回之前的指数。代码相当简单：
x = 0; # Exponent
bX = 1; # b^Exponent
while (bx <= n) {
x++;
bX *= b;
}
return x - 1;
这是多快？请注意，内部循环向上计数 x = 0、x = 1、x = 2 等，直到最终我们达到 x = ⌊log b x⌋，每次迭代进行一次乘法。如果我们假设所有和我们打交道的配合为单个机器字整数-比方说，我们正在使用int或long或类似的东西-那么每个乘法需要时间O（1），整体运行时间为O（日志b N） ，内存使用量为 O(1)。
有一个旧的面试问题是这样的。我有一个数字 n，我不会告诉你它是什么。您可以进行“x 是否等于 n、小于 n 或大于 n？”形式的查询，并且您的目标是使用最少的查询来确定 n 是什么。假设您实际上不知道 n 可以是什么，一种合理的方法是这样工作的：猜测值 1, 2, 4, 8, 16, 32, ..., 2 k , ...，直到超过 n。此时，在您刚刚找到的范围上使用二分搜索来发现 n 是什么。这在时间 O(log n) 中运行，因为在计算 2 1 + log 2 n = 2n 之后，您将超过 n，然后您在大小 n 的范围内进行二进制搜索，总运行时间为 O(log n ）。
从某种意义上说，求对数有点符合这个问题。我们有一个数 n 写成 b x表示某个未知的 x，我们想找到 x。使用上述策略作为起点，我们因此可以计算 b 2 0、b 2 1、b 2 2等，直到我们超过 b x。从那里，我们可以运行二次二分搜索来找出所需的确切指数。
我们可以通过使用以下事实来计算值系列 b 2 k
b 2 k+1 = b 2 · 2 k = (b 2 k ) 2
并找到一个过冲的值，如下所示：
x = 1; # exponent
bX = b; # b^x
while (bX <= n) {
bX *= bX; # bX = bX^2
x *= 2;
}
# Overshot, now do the binary search
问题是如何进行二分搜索来解决问题。具体来说，我们知道 b 2 x太大，但我们不知道有多大。与“猜数字”游戏不同，对指数进行二进制搜索有点棘手。
一个可爱的解决方案是基于这样的想法：如果 x 是我们正在寻找的值，那么我们可以将 x 写成一系列二进制位。例如，让我们写 x = a m-1 2 m-1 + a m-2 2 m-2 + ... + a 1 2 1 + a 0 2 0。然后
b x = b a m-1 2 m-1 + a m-2 2 m-2 + ... + a 1 2 1 + a 0 2 0
= 2 a m-1 2 m-1 · 2 a m-2 2 m-2 · ... · 2 a 0 2 0
换句话说，我们可以尝试通过一次一位地建立 x来发现 b x是什么。为此，当我们计算值 b 1、 b 2、 b 4、 b 8等时，我们可以写下我们发现的值。然后，一旦我们超调，我们可以尝试将它们相乘，看看哪些应该包括在内，哪些应该排除。这是它的样子：
x = 1; // Exponent
bX = b; // b^x
powers = [b]; // b^{2^0}
exps = [1]; // 2^0
while (bX <= n) {
bX *= bX; // bX = bX^2
powers += bX; // Append bX
x++;
exps += x;
}
# Overshot, now recover the bits
resultExp = 1
result = 0;
while (x > 0) {
# If including this bit doesn't overshoot, it's part of the
# representation of x.
if (resultExp * powers[x] <= n) {
resultExp *= powers[x];
result += exps[x];
}
x--;
}
return result;
这当然是一种更复杂的方法，但速度更快。由于我们正在寻找的值是 ⌊b x ⌋并且我们基本上是使用“猜数字游戏”中的解决方案来找出 x 是什么，乘法的次数是 O(log log b n)，其中O(log log b n)的内存使用量来保持中间功率。这比以前的解决方案快得多！
对之前的方法略有修改，保持 O(log log b n)的运行时间，但将辅助空间使用量降至 O(1)。这个想法是，我们不是使用常规系统以二进制形式写出指数，而是使用Zeckendorf 定理写出数字，这是一个基于斐波那契数列的二进制数字系统。优点是不必存储 2 的中间幂，我们可以利用这样一个事实，即任何两个连续的斐波那契数都足以让您计算下一个或前一个斐波那契数，从而允许我们根据需要重新生成 b 的幂。这是该想法在 C++ 中的实现。
在某些情况下，您需要找到对数底为 2 的对数。在这种情况下，您可以利用以下事实：计算机上的数字以二进制表示，并且乘以和除以二对应于位移。
例如，让我们采用之前的迭代乘法方法，我们计算 b 的越来越大的幂，直到超出。我们可以使用位移来实现相同的技术，而且速度要快得多：
x = 0; # Exponent
while ((1 << x) <= n) {
x++;
}
return x - 1;
这种方法仍然像以前一样在 O(log n) 时间内运行，但这种方式可能比乘法更快地实现，因为 CPU 可以更快地进行位移。
以二进制形式表示的数字的以 2 为底的对数，相当于该数字最高有效位的位置。为了找到那个位，我们可以使用类似于方法 2 的二分搜索技术，但速度更快，因为机器可以在单个指令中并行处理多个位。基本上，和以前一样，我们生成序列 2 2 0、 2 2 1等，直到我们超过这个数字，给出最高位可以有多高的上限。从那里，我们进行二进制搜索以找到最高的 1 位。这是它的样子：
x = 1;
while ((1 << x) <= n) {
x *= 2;
}
# We've overshot the high-order bit. Do a binary search to find it.
low = 0;
high = x;
while (low < high) {
mid = (low + high) / 2;
# Form a bitmask with 1s up to and including bit number mid.
# This can be done by computing 2^{m+1} - 1.
mask = (1 << (mid + 1)) - 1
# If the mask overlaps, branch higher
if (mask & n) {
low = mid + 1
}
# Otherwise, branch lower
else {
high = mid
}
}
return high - 1
这种方法在时间 O(log log n) 内运行，因为二分搜索在被搜索的数量上花费对数时间，而我们正在搜索的数量是 O(log n)。它使用 O(1) 辅助空间。
方法 5 中的加速主要是因为我们可以使用单个按位运算并行测试多个位。通过使用机器字做一些真正令人惊奇的事情，可以利用这种并行性仅使用基本的算术运算和位移位来在时间 O(1) 中找到数字中的最高有效位，并且这样做的方式是运行时间完全独立于机器字的大小（例如，该算法在 16 位、32 位和 64 位机器上同样快速地工作）。所涉及的技术相当复杂，我承认直到最近我在教授高级数据结构课程时学习了这项技术时，我才知道这是可能的。
总而言之，这里列出了这些方法、它们的时间复杂度和它们的空间复杂度。
Approach Which Bases? Time Complexity Space Complexity
--------------------------------------------------------------------------
Iter. Multiplication Any O(log_b n) O(1)
Repeated Squaring Any O(log log_b n) O(log log_b n)
Zeckendorf Logarithm Any O(log log_b n) O(1)
Bitwise Multiplication 2 O(log n) O(1)
Bitwise Binary Search 2 O(log log n) O(1)
Word-Level Parallelism 2 O(1) O(1)
还有很多我没有在这里提到的算法值得探索。一些算法的工作原理是将机器字分割成一些固定大小的块，预先计算每个块中前 1 位的位置，然后一次测试一个块。这些方法的运行时间取决于机器字的大小，并且（据我所知）没有一种方法比我在此处概述的方法渐进快。其他方法通过使用以下事实来工作：某些处理器具有立即输出数字中最高有效位位置的指令，或者通过使用浮点硬件来工作。这些也很有趣和引人入胜，一定要看看！
另一个值得探索的领域是当您拥有任意精度的整数时。在那里，乘法、除法、移位等的成本不是O(1)，并且这些算法的相对成本会发生变化。如果您好奇，这绝对值得更深入地探索！
此处包含的代码是用伪代码编写的，因为它主要是为说明而设计的。在实际实现中，您需要担心溢出，处理输入为负或零的情况等。仅供参考。:-)
希望这可以帮助！