algorithm - 从 4 位整数流中查找中值的空间使用下限。为什么它是“log n”位？

Question

今天在课上（算法课），教授说从n个4位整数的流中求中位数的空间使用下限（以位为单位）是log n。知道为什么这是真的吗？

标签： algorithmstreamspace-complexity

Answer 1

直观地说，Θ(log n) 位足以写出您看到 16 个可能的 4 位值中的每一个的次数，然后您就可以计算出中位数。为什么你不能（渐近地）改进这一点背后的直觉是，如果你使用更少的位，你甚至不记得你看过每个数字多少次，所以你不能总是返回中位数。

我要在这里提出的正式论证的要点如下。想象一下，我将输入的前半部分流式传输到您的算法中。如果你没有足够的内存，你就无法唯一记住那个输入是什么。如果你不记得那个输入是什么，那么我可以通过恶意选择数字序列的后半部分来强制你的算法给出错误的答案。

为了形式化这一点，假设您有一个算法声称使用 o(log n) （顺便说一下，这是 log n 的小 o）位来解决这个问题。现在，假设我有一个“足够大”的 n = 2k + 1 个数字流，每个数字有 4 位长。由于您使用的是 o(log n) 位内存，并且我选择 n 为“足够大”，我们可以说您的算法使用的内存严格少于 log (n - 1) - 1 = log ( 2k) - 1 = 1 + log k - 1 = log k 位内存。

现在，考虑以下 k 个选项，用于通过您的算法流式传输的 4 位数字序列。第一个是 k 个 0000 的副本。第二个是 k-1 个 0000 的副本，然后是 1 个 1111 的副本。第三个是 k-2 个 0000 的副本，然后是 2 个 1111 的副本。更一般地说，有一个序列对于 k+1 中的每一个，选择 0000 的一些副本和 1111 的一些副本。

现在，通过您的算法运行这些 k+1 个可能选项中的每一个。您使用的内存严格少于 log k 位，因此这些内存位可以包含的可能组合少于 2 ^{log k = k。这是一个问题，因为我有 k+1 个不同的序列。}因此，必须有两个序列在​​运行您的算法时会导致算法的内存最终处于相同的状态。假设第一个有 s 个 0000 副本，第二个有 t 个 0000 副本，其中 s < t。

请注意，我们只将流的 k 个元素馈送到您的算法中，因此我们仍有 k+1 个剩余元素可供选择。如果我选择它们以便恰好有 ks 个 0000 的副本，而其余的 s + 1 个元素是 1111，该怎么办？好吧，在那种情况下，看看会发生什么。

• 取 s 个 0000 副本的原始序列，然后是 ks 个 1111 副本，并通过算法运行它。然后给它 ks 个 0000 副本和 s+1 个 1111 副本。整个流现在有 k 个 0000 副本和 k+1 个 1111 副本，这意味着中位数是 1111。
• 取 0000 的 t > s 副本的原始序列，然后是 1111 的 kt < ks 副本，并通过算法运行它。然后给它 ks 个 0000 副本和 s+1 个 1111 副本。整个流现在至少有 k+1 个 0000 副本，最多有 k 个 1111 副本，所以中位数应该是 0000。

但是在这里我们遇到了一个问题。在看到输入的前半部分后，算法的状态是相同的，并且我们已经输入了与输入的后半部分相同的序列，因此算法在上述两种情况下的行为方式应该相同。但它不能，因为正如我们在这里看到的，输出应该是不同的。这对于任何确定性算法都是不可能的！

顺便说一句，这种论证风格是基于愚弄集的思想，它是一组输入，使得任何两个输入都至少有一个可以附加的后缀来区分这两个输入。它与常规语言的Myhill-Nerode 定理有关，您可以将任何具有有限内存的确定性流算法视为 DFA，每个内存位组合一个状态。