本文介绍一种根据算法产生的信息量来定性判断其是否有改进余地的方法。这个很简单的思路是前几年想到的，上周又应用了一次，找地方记录一下。
举个例子：找出 \(n\) 个未排序数字中最小的 \(k\) 个，\(n \gg k\)。
方法一：先排序，再取前面 \(k\) 个数，时间复杂度 \(O(n \log n)\)。
这个算法是不是最优的呢？我们可以对比一下目标和结果：
- 目标：找出最小的 \(k\) 个数；
- 结果：最小的 \(k\) 个数，并且按照大小排序。
可以看到，虽然排序的方法能够解决问题，但结果相对目标而言太强了，我们还得到了额外的信息——原来的问题里并不要求结果是有序的。子曰，天下没有免费的午餐，这些额外的信息必然会带来额外的开销。这个时候就应该意识到，很可能有更高效（更经济）的算法存在。
方法二：用前 \(k\) 个数字建立一个大小为 \(k\) 的 max-heap，然后依次将剩下的 \(n-k\) 个数字 \(d_i, i \in [k+1, n]\) 和堆顶数字 \(d_{top}\) 比较，若 \(d_i\) 小于 \(d_{top}\)，将 \(d_{top}\) 替换为 \(d_i\)，并重新 heapify；否则跳过 \(d_i\)。最后得到的 \(k\) 个数就是最小的 \(k\) 个。时间复杂度 \(O(k + (n-k) \log k)\)。
比起方法一，时间复杂度降低了不少，但我们还是得到了额外的信息：我们知道了 \(k\) 个数之间的部分大小关系，比如可以在 \(O(1)\) 的时间内得到 \(k\) 个数中的最大值（堆顶的数字）。
方法三：先用 Median of medians 算法找出第 \(k\) 大的数 \(d_k\)，这一步的时间复杂度 \(O(n)\)。然后遍历数组，将小于等于 \(d_k\) 的数找出来（这里不考虑有重复数字的情况）。总的时间复杂度也是 \(O(n)\)。
其实选择 \(d_k\) 的过程也会将这 \(n\) 个数字按照大小分组，但是这个额外信息比起前两种方法得到的要弱很多，所以方法三优于前两者。实际上 \(O(n)\) 的算法已经是渐进最优的，因此我们可以断定，即便还存在效率更高的算法，在渐进意义上也不可能优于方法三了。