前言 题目出自leetcode 204，本质上是为了筛选出小于n的所有质数。三种方法： 暴力枚举 埃氏筛 欧拉筛（线性筛） 枚举法 枚举法中我们只需要从 2 到 n 判断每个数是否质数即可。对于第 i 个数来说判断是否质数，只需要看其能否被 2 到 i-1 整除，如果有可以整除的则为合数，不能整除则为质数。 进一步优化，考虑到如果 y 是 x 的因数，那么 x/y 也必然是 x 的因数，因此我们只要校验 y 或者 x/y 即可。而如果我们每次选择校验两者中的较小数，则不难发现较小数一定落在 [2, sqrt(x)] 的区间中，因此我们只需要枚举 [2, sqrt(x)] 中的所有数即可。 时间复杂度：O(n*sqrt(n)) 空间复杂度：O(1) 埃氏筛 Sieve of Eratosthenes 考虑质数 x，那么 x 的倍数一定是合数，因此可以将 2x、3x….这些 x 的倍数都标记为合数，如此一来，之后遇到这些数的时候就直接知道他们是合数，直接跳过即可。 进一步优化，不用从 2x 开始标记，而是从 x*x 开始标记，因为 2x 之前已经被 2 标记过，3x 已经被 3 标记过… 时间复杂度：O(n * logn * logn) 空间复杂度：O(n) 欧拉筛（线性筛） 在埃氏筛当中，许多合数会被重复标记，比如 6 会被 2 和 3 标记，15 会被 3 和 5 标记。由于一个合数很可能会被分解成多个不相同的质数的乘积，如 42 = 2 * 3 * 7，那么 42 就会被标记三次，造成时间复杂度上的浪费。 ...

Note 这篇几乎是https://juejin.cn/post/6844903785744056333的转载-简略版 伯努利实验 在认识为什么HyperLogLog能够使用极少的内存来统计巨量的数据之前，要先认识下伯努利试验。 伯努利试验是数学概率论中的一部分内容，它的典故来源于抛硬币。 硬币拥有正反两面，一次的上抛至落下，最终出现正反面的概率都是50%。假设一直抛硬币，直到它出现正面为止，我们记录为一次完整的试验，间中可能抛了一次就出现了正面，也可能抛了4次才出现正面。无论抛了多少次，只要出现了正面，就记录为一次试验。这个试验就是伯努利试验。 ...

外部排序算法 本文介绍这三种数据结构是因为在外部排序算法中进行多路归并时，常常需要在内存中选择多路数据中的最小值，而这三者都能实现相同的功能，因此放在一起比较。 对外部排序算法熟悉的读者可以跳过该小节。 外部排序是用于对超出计算机内存容量的大型数据集进行排序的一种算法。在排序过程中，需要将数据集分成多个较小的子集，并在内存中对每个子集进行排序，然后再将排序后的子集合并起来。这种算法通常会利用硬盘等外部存储设备来协助处理数据，因此被称为“外部排序”。 外部排序的好处和必要性在于： 内存无法装入大量待排序数据，使用外部排序算法可以避免占用过多的内存。 外部排序算法还可以通过将数据集分成多个块并对每个块进行并行处理来进一步提高性能。 多路归并算法通常使用一个优先队列（也称为最小堆）来保存各个子集中的数据。在合并过程中，首先从各个子集中读取一个元素，并将它们插入到优先队列中。队列会自动将它们排序，因此队列顶端的元素是当前最小的元素。我们将队列顶端的元素取出，并将它插入到磁盘文件中。然后我们从该元素所在的子集中读取下一个元素，并将它插入到队列中，这样队列中的元素数保持不变。这个过程一直重复，直到所有元素都被读取出来，合并完成。 堆 堆（Heap）是一种特殊的完全二叉树数据结构，分为最大堆和最小堆： 最大堆：每个节点的值都大于等于其子节点，根节点是最大值。 最小堆：每个节点的值都小于等于其子节点，根节点是最小值。 堆常用于实现优先队列，支持快速获取最大值或最小值，基本操作（插入和删除）时间复杂度为 O(logn)。 具体操作如下： 取出一个元素总是发生在堆顶，因为堆顶的元素是最小的（小顶堆中）。 使用堆中最后一个元素来填补空缺位置 对顶部元素进行下沉，如果左右孩子有比自己小的，则选择选择最小的那个进行交换。重复进行下沉操作，以满足堆的性质。即每次下沉需要进行两次比较操作 胜者树 胜者树（Winner Tree）是一种特殊的完全二叉树，用于多路归并排序。它的叶子节点表示参与归并的多个数据流，非叶子节点存储比较中获胜者（较小或较大值），根节点最终存储全局最小值或最大值。 胜者树支持快速找到当前最小值并动态更新（时间复杂度 O(logk)，k 为数据流数量），常用于归并排序和流式处理场景。 胜者树满足： 胜者树一棵完全二叉树。其中的叶结点是要排序的元素，非叶结点是两个子结点中胜者的代表。 根节点代表着所有元素中的胜者。 当每次有新的元素填充进来，需要不断上浮，每次上浮与兄弟元素比较一次即可，但是每个节点指向的是父节点，而不是兄弟节点，所以需要先拿到父节点才能拿到兄弟节点，即上浮需要两次访存 败者树 败者树是胜者树的一种变体，它也是一棵完全二叉树。和胜者树不同的是，败者树的节点存储的是败者：在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。 当每次有新的元素填充进来，需要不断上浮，每次上浮与父节点比较一次即可，即一次访存 总结 堆：每次新增元素需要下沉元素，每次下沉需要两次访存+两次比较 胜者树：每次新增元素需要上浮元素，每次上浮需要两次访存+一次比较 败者树：每次新增元素需要上浮元素，每次上浮需要一次访存+一次比较 参考 https://cloud.tencent.com/developer/article/2238630 https://silver-birch-wawa.github.io/2020/05/15/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E4%B8%BA%E4%BB%80%E4%B9%88%E8%A6%81%E7%94%A8%E8%B4%A5%E8%80%85%E6%A0%91%EF%BC%9F/