海量数据TopN问题

1. 在十万的数字中找出前100？

答：快排patition+二分，堆

2. 10亿的数字找前10万，空间给1亿？

答：（分治法加堆），时间复杂度klogk

3. 100亿数字找前10亿，空间1亿？

答：这个问题不是算法问题了，应该是在问工程上的实现，基本得靠切分到多台机器并行运算来解决，具体怎么做，看下那个64马找前四的问题。

总之，对于海量数据问题，都是用的“map-reduce”的思想来分而治之，分开局部处理，之后再汇总起来计算。

参考：

海量数据中的TOPK问题小结 - Excaliburer - 博客园

海量数据处理之top K问题 - 做个快乐的自己 - 博客园

海量数据中的TopK问题_眼映星辰的博客-CSDN博客_海量数据topk问题