我必须同意，当您第一次看到O（log n）算法时，这很奇怪……对数从何而来？但是，事实证明，有多种不同的方法可以使日志项以big-O表示法显示。这里有一些：

反复除以常数

取任意数字n；例如，16.在得到小于或等于1的数字之前，可以将n除以2多少次？对于16，我们有

16 / 2 = 8
 8 / 2 = 4
 4 / 2 = 2
 2 / 2 = 1

请注意，这最终需要完成四个步骤。有趣的是，我们还有2 2 = 4的日志。嗯… 128呢？

128 / 2 = 64
 64 / 2 = 32
 32 / 2 = 16
 16 / 2 = 8
  8 / 2 = 4
  4 / 2 = 2
  2 / 2 = 1

这花费了七个步骤，并且log 2 128 =7。这是巧合吗？不！这是有充分的理由的。假设我们将数字n除以2 i次。然后我们得到数字n / 2
i。如果我们要求解最大为1的i的值，则得到

N / 2 我 ≤1

N≤2 我

对数2 n≤i

换句话说，如果我们选择一个整数i，使得i≥log 2 n，那么在将n除以i的一半之后，我们将得到一个至多1的值。为此保证的最小i大约为log 2
n，因此，如果我们有一个除以2的算法，直到数字变得足够小，那么可以说它以O（log n）步长终止。

一个重要的细节是，将n除以哪个常数并不重要（只要它大于1）即可；如果用常数k除，则将花费log k
n步才能达到1。因此，任何将输入大小重复除以某个分数的算法都将需要O（log n）迭代来终止。这些迭代可能会花费很多时间，因此净运行时不必为O（log
n），但是步数将是对数的。

那么，这在哪里出现呢？一个经典的例子是
二进制搜索
，它是一种用于在排序数组中搜索值的快速​​算法。该算法的工作原理如下：

• 如果数组为空，则返回该元素不存在于数组中。
• 除此以外：
  • 查看数组的中间元素。
  • 如果它等于我们要寻找的元素，则返回成功。
  • 如果大于我们要寻找的元素：
  • 扔掉阵列的后半部分。
  • 重复
  • 如果小于我们要查找的元素：
  • 扔掉阵列的前半部分。
  • 重复

例如，在数组中搜索5

1   3   5   7   9   11   13

我们首先来看一下中间元素：

1   3   5   7   9   11   13
            ^

由于7> 5，并且由于对数组进行了排序，因此我们知道数字5不能在数组的后半部分，因此我们可以将其丢弃。这离开

1   3   5

现在我们来看一下中间元素：

1   3   5
    ^

由于3 <5，我们知道5不能出现在数组的前半部分，因此我们可以将前半部分数组丢掉

        5

再次，我们看一下该数组的中间部分：

        5
        ^

由于这正是我们要查找的数字，因此我们可以报告数组中确实存在5。

那么这有多有效？好吧，在每次迭代中，我们至少丢弃了剩余数组元素的一半。一旦数组为空或找到所需的值，该算法就会停止。在最坏的情况下，元素不存在，因此我们将数组的大小减半，直到用完元素。这需要多长时间？好吧，由于我们将数组不断地切成两半，因此最多可以进行O（log
n）次迭代，因为我们在运行之前不能将数组切成O（log n）次以上的一半数组元素不足。

由于同样的原因，遵循
分而治
之的一般技术（将问题切成碎片，求解那些碎片，然后将问题重新组合在一起）的算法往往在其中包含对数项-您无法继续在其中分割某些对象是O（log
n）倍的一半。您可能希望将 合并排序 作为一个很好的例子。

一次处理一位数字的值

以10为底的数字n中有几位数？好吧，如果数字中有k个数字，那么我们可以认为最大数字是10 k的某个倍数。最大的k位数字是k次的999 … 9，等于10
k +1-1。因此，如果我们知道n中有k位数字，那么我们知道n的值是最多10 k +1-1。如果我们要用n来求解k，我们得到

n≤10 k + 1-1

n + 1≤10 k + 1

对数10（n + 1）≤k + 1

（log 10（n + 1））-1≤k

从中我们得出k大约是n的以10为底的对数。换句话说，n中的位数是O（log n）。

例如，让我们考虑将两个大的数字相加的复杂性，这些数字太大而无法放入一个机器字中。假设我们有那些以10为底的数字，我们将其称为m和n。一种添加方法是通过年级学校方法-
一次将数字写出一位，然后从右到左进行操作。例如，要添加1337和2065，我们首先将数字写为

    1  3  3  7
+   2  0  6  5
==============

我们添加最后一位数字并携带1：

          1
    1  3  3  7
+   2  0  6  5
==============
             2

然后，我们添加倒数第二个（“倒数第二个”）数字并携带1：

       1  1
    1  3  3  7
+   2  0  6  5
==============
          0  2

接下来，我们添加倒数第二个（“倒数第二个”）数字：

       1  1
    1  3  3  7
+   2  0  6  5
==============
       4  0  2

最后，我们添加倒数第四（“ preantepenultimate” …我喜欢英语）数字：

       1  1
    1  3  3  7
+   2  0  6  5
==============
    3  4  0  2

现在，我们做了多少工作？我们每位数字总共进行O（1）个工作（即工作量不变），并且需要处理的总位数为O（max {log n，log
m}）。因为我们需要访问两个数字中的每个数字，所以总共有O（max {log n，log m}）复杂度。

许多算法都是从某个基数上一次工作一位获得O（log n）项。一个经典的例子是 radix
sort ，它一次将整数
排序 一位。基数排序有多种形式，但是它们通常在时间O（n log
U）中运行，其中U是要排序的最大可能整数。这样做的原因是，每次通过排序都需要O（n）时间，并且总共需要O（log
U）次迭代来处理要排序的最大数字的每个O（log
U）数字。许多高级算法（例如Gabow的最短路径算法或Ford-
Fulkerson最大流算法的缩放版本）在复杂度方面都有对数项，因为它们一次只能工作一位。

关于您如何解决该问题的第二个问题，您可能需要看一下相关的问题，以探索更高级的应用程序。考虑到此处描述的问题的一般结构，当您知道结果中有对数项时，您现在可以更好地思考问题，因此建议您在给出答案之前不要查看答案有些想法。

希望这可以帮助！