113

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

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

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

假设 X(1..n) 和 Y(1..n) 包含两个整数列表，每个列表都按非递减顺序排序。给出一个 O(log n) 时间的算法来找到所有 2n 个组合元素的中位数（或第 n 个最小整数）。例如，X = (4, 5, 7, 8, 9) 和 Y = (3, 5, 8, 9, 10)，那么 7 是组合列表的中位数 (3, 4, 5, 5, 7 , 8, 8, 9, 9, 10)。[提示：使用二分查找的概念]

4

6 回答 6

303

我不得不同意，当你第一次看到 O(log n) 算法时，这很奇怪……这个对数到底是从哪里来的？然而，事实证明，有几种不同的方法可以让日志项以大 O 表示法显示。这里有几个：

反复除以一个常数

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

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

请注意，这最终需要四个步骤才能完成。有趣的是，我们也有 log 2 16 = 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。如果我们想求解 i 的值，该值最多为 1，我们得到

n / 2 i ≤ 1

n ≤ 2我

日志2 n ≤ i

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

一个重要的细节是，你将 n 除以什么常数并不重要（只要它大于一）；如果除以常数 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 位数字是 999...9，k 次，这等于 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) 项。一个经典的例子是基数排序，它一次对整数进行一位数排序。基数排序有很多种，但它们通常运行时间为 O(n log U)，其中 U 是被排序的最大可能整数。这样做的原因是，每次排序都需要 O(n) 时间，并且总共需要 O(log U) 次迭代来处理被排序的最大数字的每个 O(log U) 位。许多高级算法，例如Gabow 的最短路径算法或Ford-Fulkerson 最大流算法的缩放版本，在其复杂性中都有一个对数项，因为它们一次只工作一个数字。

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

希望这可以帮助！

于 2012-02-05T21:56:16.400 回答
10

当我们谈论 big-Oh 描述时，我们通常谈论的是解决给定大小的问题所花费的时间。通常，对于简单的问题，该大小仅以输入元素的数量为特征，通常称为 n 或 N。（显然这并不总是正确的——图的问题通常以顶点的数量 V 和边数，E；但现在，我们将讨论对象列表，列表中有 N 个对象。）

当且仅当：

对于所有 N > 某个任意 N_0，存在某个常数 c，使得算法的运行时间小于该常数 c 倍（N 的某个函数。）

换句话说，不要考虑设置问题的“恒定开销”很重要的小问题，而要考虑大问题。并且在考虑大问题时，（N 的某个函数）的大哦意味着运行时间仍然总是小于该函数的某个常数倍。总是。

简而言之，该函数是一个上限，直到一个常数因子。

因此，“log(n) 的大哦”的含义与我上面所说的相同，只是“N 的某些函数”被替换为“log(n)”。

所以，你的问题告诉你考虑二分搜索，所以让我们考虑一下。假设您有一个按升序排序的 N 个元素的列表。您想查明该列表中是否存在某个给定的数字。一种不是二分搜索的方法是只扫描列表的每个元素，看看它是否是您的目标编号。您可能会很幸运并在第一次尝试时找到它。但在最坏的情况下，您将检查 N 个不同的时间。这不是二分搜索，也不是 log(N) 的大哦，因为没有办法强制它进入我们上面勾勒的标准。

你可以选择任意常数为 c=10，如果你的列表有 N=32 个元素，你很好：10*log(32) = 50，它大于 32 的运行时间。但是如果 N=64 , 10*log(64) = 60，小于 64 的运行时间。你可以选择 c=100，或 1000，或一个 gazillion，你仍然可以找到一些违反该要求的 N。换句话说，没有N_0。

但是，如果我们进行二分搜索，我们会选择中间元素并进行比较。然后我们扔掉一半的数字，然后再做一次，一次又一次，以此类推。如果您的 N=32，您只能执行大约 5 次，即 log(32)。如果你的 N=64，你只能这样做大约 6 次，等等。现在你可以选择任意常数 c，这样对于大的 N 值总是满足要求。

在所有这些背景下，O(log(N)) 通常意味着你有一些方法可以做一件简单的事情，这会将你的问题规模减少一半。就像上面的二分搜索一样。一旦你把问题切成两半，你就可以一次又一次地把它切成两半。但是，至关重要的是，你不能做的是一些预处理步骤，它需要比 O(log(N)) 时间更长的时间。因此，例如，您不能将两个列表混为一个大列表，除非您也能在 O(log(N)) 时间内找到一种方法。

（注意：几乎总是，Log(N) 表示以二为底的对数，这是我在上面假设的。）

于 2012-02-05T21:45:05.743 回答
4

在以下解决方案中，所有具有递归调用的行都在 X 和 Y 的子数组给定大小的一半上完成。其他行在恒定时间内完成。递归函数为 T(2n)=T(2n/2)+c=T(n)+c=O(lg(2n))=O(lgn)。

你从 MEDIAN(X, 1, n, Y, 1, n) 开始。

MEDIAN(X, p, r, Y, i, k) 
if X[r]<Y[i]
    return X[r]
if Y[k]<X[p]
    return Y[k]
q=floor((p+r)/2)
j=floor((i+k)/2)
if r-p+1 is even
    if X[q+1]>Y[j] and Y[j+1]>X[q]
        if X[q]>Y[j]
            return X[q]
        else
            return Y[j]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q+1, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j+1, k)
else
    if X[q]>Y[j] and Y[j+1]>X[q-1]
        return Y[j]
    if Y[j]>X[q] and X[q+1]>Y[j-1]
        return X[q]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j, k)
于 2012-07-13T18:40:32.270 回答
4

Log 术语在算法复杂度分析中经常出现。以下是一些解释：

1.你如何表示一个数字？

让我们取数字 X = 245436。“245436”这个符号包含隐含的信息。明确该信息：

X = 2 * 10 ^ 5 + 4 * 10 ^ 4 + 5 * 10 ^ 3 + 4 * 10 ^ 2 + 3 * 10 ^ 1 + 6 * 10 ^ 0

这是数字的十进制扩展。所以，我们需要代表这个数字的最少信息量是6位数字。这并非巧合，因为任何小于10^d的数字都可以用d位表示。

那么代表 X 需要多少位数字呢？这等于 X 中 10 的最大指数加 1。

==> 10 ^ d > X
==> log (10 ^ d) > log(X)
==> d* log(10) > log(X)
==> d > log(X) // 出现 log再次...
==> d = floor(log(x)) + 1

另请注意，这是表示此范围内数字的最简洁方式。任何减少都会导致信息丢失，因为丢失的数字可以映射到其他 10 个数字。例如：12* 可以映射到 120、121、122、...、129。

2. 如何在 (0, N - 1) 中搜索一个数？

取 N = 10^d，我们使用最重要的观察结果：

唯一标识 0 到 N - 1 = log(N) 位范围内的值的最小信息量。

这意味着，当被要求在整数行上搜索一个从 0 到 N - 1 的数字时，我们至少需要 log(N)次尝试找到它。为什么？任何搜索算法在搜索数字时都需要一个接一个地选择一个数字。

它需要选择的最小位数是 log(N)。因此，在大小为 N 的空间中搜索数字所需的最小操作数是 log(N)。

你能猜出二分查找、三元查找或十进制查找的顺序复杂度吗？
它的O(log(N))！

3. 如何对一组数字进行排序？

当被要求将一组数字 A 排序到数组 B 中时，它是这样的 ->

置换元素

原始数组中的每个元素都必须映射到排序数组中的相应索引。所以，对于第一个元素，我们有 n 个位置。为了正确找到从 0 到 n - 1 范围内的对应索引，我们需要…log(n) 操作。

下一个元素需要 log(n-1) 操作，下一个 log(n-2) 等等。总数为：

==> log(n) + log(n - 1) + log(n - 2) + … + log(1)

使用 log(a) + log(b) = log(a * b)，

==> log （嗯！）

这可以近似为 nlog(n) - n。
这是O（n * log（n））！

因此我们得出结论，没有比 O(n*log(n)) 做得更好的排序算法。一些具有这种复杂性的算法是流行的合并排序和堆排序！

这些是我们在算法的复杂性分析中经常看到 log(n) 弹出的一些原因。同样可以扩展到二进制数。我在这里制作了一个视频。
为什么在算法复杂度分析过程中log(n)会经常出现？

干杯!

于 2018-01-28T08:54:55.063 回答
2

我们称时间复杂度为 O(log n)，当解决方案基于 n 上的迭代时，每次迭代中完成的工作是前一次迭代的一小部分，因为算法朝着解决方案工作。

于 2017-07-09T17:51:49.587 回答
1

还不能发表评论……死了！Avi Cohen 的回答不正确，请尝试：

X = 1 3 4 5 8
Y = 2 5 6 7 9

没有一个条件为真，因此 MEDIAN(X, p, q, Y, j, k) 将削减两个五。这些是非递减序列，并非所有值都是不同的。

还可以尝试这个具有不同值的偶数长度示例：

X = 1 3 4 7
Y = 2 5 6 8

现在 MEDIAN(X, p, q, Y, j+1, k) 将削减四个。

相反，我提供了这个算法，用 MEDIAN(1,n,1,n) 调用它：

MEDIAN(startx, endx, starty, endy){
  if (startx == endx)
    return min(X[startx], y[starty])
  odd = (startx + endx) % 2     //0 if even, 1 if odd
  m = (startx+endx - odd)/2
  n = (starty+endy - odd)/2
  x = X[m]
  y = Y[n]
  if x == y
    //then there are n-2{+1} total elements smaller than or equal to both x and y
    //so this value is the nth smallest
    //we have found the median.
    return x
  if (x < y)
    //if we remove some numbers smaller then the median,
    //and remove the same amount of numbers bigger than the median,
    //the median will not change
    //we know the elements before x are smaller than the median,
    //and the elements after y are bigger than the median,
    //so we discard these and continue the search:
    return MEDIAN(m, endx, starty, n + 1 - odd)
  else  (x > y)
    return MEDIAN(startx, m + 1 - odd, n, endy)
}
于 2015-11-20T14:15:46.493 回答