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

Question

我对大 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）。 [提示：使用二分搜索的概念]

Answer 1

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

重复除以一个常数

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

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

这最终需要四个步骤才能完成。有趣的是，我们还有 log₂ 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₂ 128 = 7。这是巧合吗？没有！这是有充分理由的。假设我们将数字 n 除以 2 i 次。然后我们得到数字 n / 2ⁱ。如果我们想求解 i 的值，其中该值最多为 1，我们得到

n / 2ⁱ ≤ 1

n ≤ 2ⁱ

log₂ n ≤ i

换句话说，如果我们选择一个整数 i 使得 i ≥ log₂ n，那么将 n 除以 i 次之后，我们将得到一个最多为 1 的值。保证这一点的最小 i 大约为 log₂ 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 位数字是 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

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

： ，我们添加倒数第三个（“antepenultimate”）数字：

       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 最大流量算法，其复杂性有一个对数项，因为它们一次只处理一位数字。

---

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

Answer 2

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

我们说问题“是（N 的某个函数）的大哦”如果并且仅当：

对于所有N>一些任意的 N_0，有一些常数 c，这样算法的运行时间小于该常数 c 倍（N 的某个函数）。

换句话说，不要考虑其中的小问题设置问题的“持续开销”很重要，思考大问题。当考虑大问题时，（N 的某个函数）的 big-Oh 意味着运行时间仍然总是小于该函数的某个常数倍。总是。

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

因此，“log(n) 的 big-Oh”与我上面所说的意思相同，只是“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，或无数，您仍然可以找到一些违反该要求的 N 个。换句话说，不存在N_0。

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

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

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

Answer 3

在以下解决方案中，所有具有递归调用的行都在
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)

Answer 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
==>对数(10^d)>日志（X）
==> d*日志(10)>日志（X）
==> d＞ log(X) // 日志再次出现...
==> d = 下限(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), < br>
==>日志（n！）

这可以近似到nlog(n) - n。
这是 O(n*log(n))!

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

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

干杯！

Answer 5

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

Answer 6

还不能发表评论……它是死灵！
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)
}