algorithm - 什么会导致算法具有 O(log n) 复杂度？

Question

我对 big-O 的了解是有限的，当等式中出现对数项时，它会让我更加失望。

有人可以简单地向我解释一下什么是 O(log n)算法是？对数从何而来？

当我试图解决这个期中练习题时，特别出现了这个问题:

Let X(1..n) and Y(1..n) contain two lists of integers, each sorted in nondecreasing order. Give an O(log n)-time algorithm to find the median (or the nth smallest integer) of all 2n combined elements. For ex, X = (4, 5, 7, 8, 9) and Y = (3, 5, 8, 9, 10), then 7 is the median of the combined list (3, 4, 5, 5, 7, 8, 8, 9, 9, 10). [Hint: use concepts of binary search]

Answer 1

我必须同意，当您第一次看到 O(log n) 算法时，这很奇怪……那个对数到底来自哪里？然而，事实证明，有几种不同的方式可以让对数项以大 O 表示法显示。以下是一些:

重复除以一个常数

取任意数 n;比如说， 16. 在得到一个小于或等于 1 的数之前，你可以将 n 除以 2 多少次？对于 16，我们有

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

请注意，这最终需要四个步骤才能完成。有趣的是，我们还有 log2 16 = 4。嗯……128 怎么样？

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

这需要七步，log2 128 = 7。这是巧合吗？不!这是有充分理由的。假设我们将一个数 n 除以 2 i 次。然后我们得到数字 n/2i。如果我们想求解 i 的值，该值最多为 1，我们得到

n / 2ⁱ ≤ 1

n ≤ 2ⁱ

log₂ n ≤ i

换句话说，如果我们选择一个整数 i 使得 i ≥ log2 n，那么在将 n 一分为二 i 次后，我们将得到一个至多为 1 的值。 保证这一点的最小 i 大约是 log2 n，所以如果我们有一个算法除以 2 直到数字变得足够小，那么我们可以说它以 O(log n) 步终止。

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

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

如果数组为空，则返回该元素不存在于数组中。

否则:

查看数组的中间元素。

如果它等于我们正在寻找的元素，则返回成功。

如果它大于我们正在寻找的元素:

扔掉数组的后半部分。

重复

如果它小于我们要查找的元素:

扔掉数组的前半部分。

重复

例如，在数组中搜索 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) 次超出数组元素。

遵循 通用技术的算法divide-and-conquer (将问题分成几部分，解决这些部分，然后将问题重新组合在一起)出于同样的原因，其中往往包含对数项 - 您不能将某个对象切成两半以上 O(log n) 次。您可能想查看 merge sort作为这方面的一个很好的例子。

一次处理一位数值

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

n ≤ 10^k+1 - 1

n + 1 ≤ 10^k+1

log₁₀ (n + 1) ≤ k + 1

(log₁₀ (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's shortest-paths algorithm或 Ford-Fulkerson max-flow algorithm 的缩放版本，在它们的复杂性上有一个对数项，因为它们一次只处理一个数字。

至于你如何解决这个问题的第二个问题，你可能想看看 this related question它探索了更高级的应用程序。鉴于此处描述的问题的一般结构，当您知道结果中有对数项时，您现在可以更好地了解如何思考问题，因此我建议您在给出答案之前不要查看答案一些想法。

希望这有帮助!