通信复杂度问题：确定双方手中所有数的中位数

通信复杂度（communication complexity）主要研究这么一类问题： A 持有数据 x ， B 持有数据 y ，他们想要合作计算某个关于 x 和 y 的二元函数值 f(x, y) ，那么在渐近意义下，两人至少需要传输多少 bit 的数据。最近着迷于通信复杂度，看到了几个与通信复杂度有关的问题，和大家分享一下。下面就是其中之一。

A 、 B 的手中各有一个 {1, 2, …, n} 的子集。两人想知道，如果把他们手中的数全都放在一块儿，那么这些数（可能会有重复的数）的中位数是多少。然而， A 、 B 两人远隔千里，他们之间通信的成本非常高。因此，他们想在通信线路上传输尽可能少的信息，使得最终两人都知道中位数的值。在这里，为了简便起见，我们直接定义 m 个数的中位数是第 ⌈ m / 2 ⌉ 小的数，因而如果 m = 2k ，那么中位数就应该直接取第 k 小的数。

其中一种最笨的方法是， A 把手中的所有数全部发给 B 。由于发送一个不超过 n 的正整数最多会用到 log(n) 个 bit ，而 A 手里的数最多有 O(n) 个，因此 A 传给 B 的信息量就是 O(n · logn) 。于是， B 就得到了足够多的信息，可以直接计算中位数了，算好后再把结果告诉 A ，此时又要耗费 log(n) 个 bit （但它并不会成为通信量的瓶颈）。因此，在这种方案中，总的通信复杂度就是 O(n · logn) 。事实上，传送一个 {1, 2, …, n} 的子集只需要一个 n 位 01 串就够了，因而我们可以把通信复杂度降低到 O(n) 个 bit 。

利用下面的办法，我们可以实现 O(logn · logn) 的通信复杂度。首先， A 、 B 分别告诉对方自己手中有多少个数，这一共会耗费 O(logn) 个 bit 。接下来，两人在区间 [1, n] 上进行二分查找。假设到了某一步，中位数被限定在了区间 [i, j] 里，那么 A 就计算出 k = (i + j) / 2 ，数一数自己手中有多少个数比 k 小，然后告诉 B ，由 B 再来数数自己这边又有多少个比 k 小的数，从而判断出 k 作为中位数来说是偏大了还是偏小了，并把判断出来的结果返回给 A 。根据情况，区间 [i, j] 将被更新为 [i, k] 或者 [k, j] ，两人在新的区间上继续二分下去。整个算法将会持续 O(logn) 轮，每一轮都会传输 O(logn) 的数据，因此总的通信复杂度是 O(logn · logn) 。

另一方面，通信复杂度至少是 Ω(logn) 的。这是因为，如果规定 A 和 B 最多只能交流 k 个 bit ，那么整个交流历史最多就只有 k 次分岔的机会，到最后最多只能产生 2^k个不同的分支；但事实上中位数有可能是 1 到 n 中的任何一个，共有 n 种不同的可能，因此 2^k必须大于等于 n 。这说明 k 必须大于等于 log₂(n) ，也就是说两个人总会有必须要交流 log₂(n) 个 bit 才行的时候。

一个有意思的问题自然而然地诞生了：我们所得的上界和下界仍然有差距。究竟是刚才的算法还不够经济，还是刚才证明的结论还不够强呢？

还想说明一点的是，两个人商量算法的过程，或者其中一个人把算法告诉另一个人的过程，这可以不算进通信复杂度里。事实上，把它们算进通信复杂度里也没关系，因为它们反正都是 O(1) 的。

我们还能把通信复杂度进一步降低到 O(logn) ，从而完美地解决这个问题。为此，我们先给出另一种 O(logn · logn) 的算法，然后把它改进到 O(logn) 去。

假设 A 和 B 手中的数分别有 |A| 个和 |B| 个，而且正好有 |A| = |B| = 2^k，其中 k 是某个正整数。如果不是的话，可以让 A 先花费 O(logn) 个 bit 把 |A| 告诉 B ，同样地， B 也花费 O(logn) 个 bit 把 |B| 告诉 A 。然后，两人找出一个最小的但是比 |A| 和 |B| 都大的 2^k。接下来，两个人都在自己的数据当中加入 1 和 n ，把各自手中的数填充到 2^k个。只要最后两个人总共加入了同样多的 1 和 n （或者加进去的 n 比加进去的 1 多一个，如果 |A| + |B| 是奇数的话），这都不会改变中位数的值。两人可以花费 O(logn) 个 bit 来约定，每个人都往自己的数据里加入多少个 1 和多少个 n 。注意，虽然两个人手中的数变多了，但从对数意义上看，这仅仅是常数级别的变化。

现在，每个人手中都有 2^k个数了。每个人都给自己手中的所有数从小到大排个序。假设此时 A 手中所有数的中位数是 a ， B 手中所有数的中位数是 b 。两人用 O(logn) 个 bit 交换 a 和 b 的值。如果 a < b ，那么 A 手中前面一半的数肯定不可能是中位数了， A 就把前面一半的数丢掉；同时， B 手中后面一半的数肯定也不可能是中位数，因此 B 就可以把他手中后面一半的数都丢掉。类似地，如果 a > b ，那么 A 就可以把他后面一半的数丢掉， B 就可以把他前面一半的数丢掉。不管怎么样， A 、 B 两人手里的数都只剩下原来的一半了，并且如果把两个人手中的数合起来看，那么真正的中位数左右两边都被去掉了同样多的数，因而剩下的数将会保持中位数不变。接下来， A 算出新的 a 是多少， B 算出新的 b 是多少，然后两人再次比较 a 和 b ，并继续扔掉各自手里其中一半的数……不断这样做下去，那么每个人手中的数都会成半地减少。等到哪一步，两个人手里都只剩一个数了，小的那个数一定就是中位数了；或者某一步出现了 a = b 的情况，那么这个值就一定是中位数了。整个过程一共有 O(logn) 轮，每一轮都会传输 O(logn) 的数据，因此总的通信复杂度是 O(logn · logn) 。

现在，我们把算法的通信复杂度改进到 O(logn) 。首先注意到，在每一轮当中，双方并不需要知道 a 和 b 的值，只需要知道 a 和 b 谁更大一些。因此，两个人可以从高到低轮流发送 a 和 b 的二进制位，一旦出现不同就可以立即停下来了。另外，如果这一轮逐位比较大小的时候，到了左起第 i 位才比出 a 和 b 的大小，那么对于今后的 a 和 b 来说，我们要么根本就不用比较，要么就可以直接从第 i 位开始比较。比方说，在这一轮里双方发现 a = 00100????? 并且 b = 00101????? ，这就说明 a < b 。此时， A 会去掉前面一半的数，那些头几位就比 00100 小的数肯定都被去掉了，剩下的数只有可能以 00100, 00101, 00110, 00111, 01000, … 打头；类似地， B 则会去掉后面一半的数，剩下的数只能以 00101, 00100, 00011, 00010, … 打头。假如今后某一轮中的 a 值是以 00110 打头的，那么 A 不用跟 B 说话就能直接知道，这回肯定是 a 值更大一些 ，因为 B 的手里不可能有这么大的数，它们都已经被去掉了。此时， A 就可以用 O(1) 个 bit 直接告诉 B ，这回我的 a 肯定比你的 b 大，咱俩该怎么办就怎么办吧。类似地，今后 B 也可能会出现这样的情况：一看 b 值的头几位，直接就知道该怎么办了。除非 a 和 b 都以 00100 或者 00101 打头，我们才真的需要比较 a 和 b 的大小，因此我们可以直接从上次停止的数位开始继续往下比。

如果某一轮当中比到了相同的位，那么这些位今后就再也不用交换了，而 a 和 b 都有 O(logn) 位，这说明两人一共交换了 O(logn) 次相同的位；如果某一轮当中比到了不同的位，那么这一轮比较就会立即停止，这说明每一轮里最多只会遇到一次不同的位，而整个算法有 O(logn) 轮，因而两人一共也就交换了 O(logn) 次不同的位。另外，整个算法开始前会有 O(logn) 的交流（为了把数据填充到 2^k个），每一轮也会产生 O(1) 的交流（告诉对方是否需要比较）。因而，最终总的通信复杂度就是 O(logn) 。

参考资料： Eyal Kushilevitz and Noam Nisan, Communication complexity.