space 的下限用于从 4 位整数流中查找中位数。为什么是 'log n' 位？
Lower bound of space usage for finding median from stream of 4-bit integers. Why is it 'log n' bits?
今天，在 class（算法 class）期间，教授说 space 的下限使用（以位为单位）用于从 n 4 位流中查找中值整数是 log n。知道为什么这是真的吗？
直觉上，Θ(log n) 位足以写出您已经看到 16 个可能的 4 位值中的每一个的次数，然后您可以从那里计算中位数。为什么你不能（渐进地）对此进行改进背后的直觉是，如果你使用更少的位，你甚至不记得你看到每个数字多少次，所以你不能总是 return中位数.
我要在这里进行的正式论证的要点如下。想象一下，我将输入的前半部分流式传输到您的算法中。如果你没有足够的内存位，你就无法唯一地记住那个输入是什么。如果你不记得那个输入是什么，那么我可以通过恶意选择数字序列的后半部分来强制你的算法给出错误答案。
为了将其形式化，我们假设您有一个算法声称可以使用 o(log n)（顺便说一下，即 little-o of log n）内存位来解决此问题。现在，假设我有一个“足够大”的 n = 2k + 1 数字流，每个数字有四位长。由于您正在使用 o(log n) 位内存并且我选择 n 为“足够大”，我们可以说您的算法使用的内存严格少于 log (n - 1) - 1 = log ( 2k) - 1 = 1 + log k - 1 = log k 内存位。
现在，考虑以下 k 个 4 位数字序列的选择，以流过您的算法。第一个是 0000 的 k 个副本。第二个是 0000 的 k-1 个副本，然后是 1111 的 1 个副本。第三个是 0000 的 k-2 个副本，然后是 1111 的 2 个副本。更一般地说，有一个序列对于 0000 的一些副本和 1111 的一些副本的 k+1 个不同选择中的每一个。
现在，运行 这 k+1 个可能的选项中的每一个都通过您的算法。您使用的内存位严格少于 log k 位，因此这些内存位可以包含的可能组合少于 2log k = k。这是个问题，因为我有 k+1 个不同的序列。因此，当 运行 通过您的算法时，必须有两个序列导致算法的内存最终处于相同状态。假设第一个有 s 个 0000 的副本，第二个有 t 个 0000 的副本，其中 s < t.
请注意，我们只将流中的 k 个元素输入到您的算法中，因此我们还有 k+1 个剩余元素可供选择。如果我选择它们使得 0000 恰好有 k-s 个副本，其余 s + 1 个元素为 1111 怎么办？好吧，既然如此，看看会发生什么。
- 采用 0000 的 s 个副本的原始序列，然后是 1111 的 k-s 个副本，然后通过算法 运行 它。然后给它k-s份0000和s+1份1111。现在整个流有k份0000和k+1份1111，也就是说中位数是1111。
- 采用原始序列 t > s 个 0000 的副本，然后是 k-t < k-s 个 1111 的副本，然后通过算法 运行 它。然后给它k-s份0000和s+1份1111。现在整个流至少有k+1份0000，最多k份1111，所以中位数应该是0000。
但是这里我们运行遇到了问题。在看到输入的前半部分后，算法的状态是相同的，并且我们输入了与输入的后半部分相同的序列，因此算法在上述两种情况下的行为方式应该相同。但它不能，因为正如我们在这里看到的那样，输出应该是不同的。这对任何确定性算法来说都是不可能的！
顺便说一下，这种论证方式是基于 fooling set, which is a set of inputs such that any two inputs have at least one suffix that can be tacked on that distinguishes those two inputs. It's related to the Myhill-Nerode theorem 常规语言的想法，您可以将任何具有有限内存的确定性流算法视为每个组合具有一个状态的 DFA内存位。
今天，在 class（算法 class）期间，教授说 space 的下限使用（以位为单位）用于从 n 4 位流中查找中值整数是 log n。知道为什么这是真的吗？
直觉上，Θ(log n) 位足以写出您已经看到 16 个可能的 4 位值中的每一个的次数，然后您可以从那里计算中位数。为什么你不能（渐进地）对此进行改进背后的直觉是，如果你使用更少的位，你甚至不记得你看到每个数字多少次，所以你不能总是 return中位数.
我要在这里进行的正式论证的要点如下。想象一下，我将输入的前半部分流式传输到您的算法中。如果你没有足够的内存位，你就无法唯一地记住那个输入是什么。如果你不记得那个输入是什么，那么我可以通过恶意选择数字序列的后半部分来强制你的算法给出错误答案。
为了将其形式化，我们假设您有一个算法声称可以使用 o(log n)（顺便说一下，即 little-o of log n）内存位来解决此问题。现在，假设我有一个“足够大”的 n = 2k + 1 数字流，每个数字有四位长。由于您正在使用 o(log n) 位内存并且我选择 n 为“足够大”，我们可以说您的算法使用的内存严格少于 log (n - 1) - 1 = log ( 2k) - 1 = 1 + log k - 1 = log k 内存位。
现在，考虑以下 k 个 4 位数字序列的选择，以流过您的算法。第一个是 0000 的 k 个副本。第二个是 0000 的 k-1 个副本，然后是 1111 的 1 个副本。第三个是 0000 的 k-2 个副本，然后是 1111 的 2 个副本。更一般地说，有一个序列对于 0000 的一些副本和 1111 的一些副本的 k+1 个不同选择中的每一个。
现在，运行 这 k+1 个可能的选项中的每一个都通过您的算法。您使用的内存位严格少于 log k 位，因此这些内存位可以包含的可能组合少于 2log k = k。这是个问题，因为我有 k+1 个不同的序列。因此，当 运行 通过您的算法时，必须有两个序列导致算法的内存最终处于相同状态。假设第一个有 s 个 0000 的副本，第二个有 t 个 0000 的副本，其中 s < t.
请注意，我们只将流中的 k 个元素输入到您的算法中，因此我们还有 k+1 个剩余元素可供选择。如果我选择它们使得 0000 恰好有 k-s 个副本，其余 s + 1 个元素为 1111 怎么办？好吧，既然如此，看看会发生什么。
- 采用 0000 的 s 个副本的原始序列，然后是 1111 的 k-s 个副本，然后通过算法 运行 它。然后给它k-s份0000和s+1份1111。现在整个流有k份0000和k+1份1111，也就是说中位数是1111。
- 采用原始序列 t > s 个 0000 的副本，然后是 k-t < k-s 个 1111 的副本，然后通过算法 运行 它。然后给它k-s份0000和s+1份1111。现在整个流至少有k+1份0000，最多k份1111，所以中位数应该是0000。
但是这里我们运行遇到了问题。在看到输入的前半部分后，算法的状态是相同的，并且我们输入了与输入的后半部分相同的序列，因此算法在上述两种情况下的行为方式应该相同。但它不能，因为正如我们在这里看到的那样，输出应该是不同的。这对任何确定性算法来说都是不可能的！
顺便说一下，这种论证方式是基于 fooling set, which is a set of inputs such that any two inputs have at least one suffix that can be tacked on that distinguishes those two inputs. It's related to the Myhill-Nerode theorem 常规语言的想法，您可以将任何具有有限内存的确定性流算法视为每个组合具有一个状态的 DFA内存位。