数据范围决定算法选型：从O(n log n)到O(n)

我去年处理过一个挺有意思的活儿某内部工具需要在上亿条日志里按时间窗口做聚合统计数据的时间戳全部落在最近三个月内。一开始我按教科书思路上了红黑树、跳表这类“高级”结构结果在真实数据上跑得还不如后来换上的一个普通数组快。原因很简单——我知道时间戳的确定范围明明可以用直接定址的思路偏要去搞那些对范围无感的通用结构。这件事给我的教训很直接算法选型先看数据范围范围一旦已知很多“复杂度更优”的通用方案反而会被一个最朴素的数组下标干掉。这篇内容就想把“根据已知数据范围选择算法”这个话题掰开揉碎。我适合以下人群阅读写业务代码时经常面对确定值域的数据比如用户ID、订单号、IP段、时间戳、固定枚举状态却不太确定该用哈希、树还是数组的人刷题或做竞赛时知道数据范围却总选错算法的人以及工作中需要评估算法选型、做性能优化的人。看完你就明白范围信息不是可有可无的细节而是能把算法复杂度从 O(n log n) 拉到 O(n) 甚至 O(1) 的关键钥匙。1. “已知数据范围”为什么能改变算法抉择——从时间复杂度的盲区说起大多数人学算法时最先接触的是时间复杂度的渐进分析。这个工具很强大但它有一个致命盲区复杂度公式里往往只出现 n元素个数而不出现 U值域大小。结果就是当问题里同时存在 n 和 U 这两个维度时仅看 n 会严重误导选型方向。1.1 一个反直觉的例子知道范围后“笨算法”反而最快先看一个最经典的场景给 10^7 个整数排序这 10^7 个数全部落在区间 [0, 10^5] 内。常规思路是快速排序或归并排序复杂度 O(n log n)。n 10^7 时10^7 × log2(10^7) ≈ 10^7 × 23.25大约 2.3 亿次基本操作。跑起来一般需要几百毫秒到一秒多具体看语言和优化情况。但如果我知道所有数都落在 [0, 10^5] 这个有限范围内可以用计数排序// 已知arr[0..n-1] 中所有元素满足 0 arr[i] U_MAX (U_MAX 100000) void countingSort(vectorint arr, int U_MAX) { vectorint cnt(U_MAX 1, 0); for (int x : arr) cnt[x]; int idx 0; for (int v 0; v U_MAX; v) { while (cnt[v]--) arr[idx] v; } }这段代码的复杂度是 O(n U)其中 U 10^5。两层循环加起来只有 10^7 10^5 的量级大约 1010 万次操作比快速排序的 2.3 亿次少了二十多倍。这里的关键不是“计数排序打败快排”而是“在范围已知的情况下复杂度分析必须同时考虑 n 和 U 两个变量否则会得到错误结论”。如果你只会背“快排就是 O(n log n) 最优”面对这种确定值域的数据就会错过一个数量级的性能提升。1.2 数据范围如何改变“最优解”的定义数据范围至少包含以下几个维度每个维度都直接影响选型维度含义示例影响的算法选择值域上界 U元素最大可能取值0 ~ 10^5、0 ~ 2^31-1决定能否用数组直接定址连续性值域是否基本连续用户ID是否从0递增分配决定数组是否浪费空间密集程度实际出现的元素数量 vs 值域大小稀疏与密集数组 vs 哈希表重复程度是否有大量重复元素状态枚举值计数排序 vs 比较排序偏移量最小值是否远大于0时间戳、ID从大数开始是否做映射、平移分布形态均匀、偏斜、幂律长尾数据基数排序 vs 计数排序举一个直观类比假设你要给一万个盒子贴上对应编号的标签每个盒子上的编号从 1 到 10000。如果你提前知道“编号范围就是 1 到 10000”最蠢也最有效的办法是准备一万个空位看见几号盒子就放到几号位子上如果你不知道编号范围就得把所有盒子排成一排一个个比较交换排序。前者就是“范围已知”的威力——你不需要通过互相比较来推断位置而是直接把“值”当成“位置”。理解了这个前提下面就可以进入实际操作层面的拆解了。2. 四个高频场景的选型拆解排序、查找、去重、素数处理范围信息对算法选型的影响在排序、查找、去重、素数这四个场景里体现得最充分。我分别把它们的决策逻辑讲透。2.1 排序场景计数排序碾压快排的边界在哪里计数排序的思路本质上是“用空间换时间”它把数据本身当作数组下标先统计每个值出现多少次再按值从小到大把元素回填。它成立的条件很苛刻但也很明确元素必须是非负整数值域 U 不能太大而且你能容忍排序后的元素只是数值有序大多时候这足够了。当 U 远小于 n 时计数排序几乎无敌当 U 和 n 同量级比如 n 10^7、U 10^7那么 O(n U) 和 O(n log n) 差别不大这时反而要考虑内存占用和常数因子。一个实际的选择标准可以写成U ≤ 10^7内存允许 4U 字节int 数组时优先考虑计数排序如果数据中有负数先做平移把最小值变为0如果不只是简单排序还需要按其他键二次排序改用基数排序或“计数排序稳定归并”。基数排序值得多说一句。它是计数排序的推广把整数按位拆成多个关键字每一位分别做一次稳定的计数排序。比如 32 位整数可以按 8 位一组分成 4 轮。这样即使 U 很大接近 2^32只要数据本身分布均匀也能在 O(n × 位数/组大小) 内排完大约就是 O(4n)。所以面对 0 到 2^32-1 的大范围整数排序基数排序是比快速排序更贴近“工程最优”的选择之一。这里有一个需要警惕的误区有些资料说“计数排序适合小范围”但没定义“小”到底是多少。在很多竞赛和面试场景里值域 10^6 以下才算“小”但在真实系统里如果内存很充裕10^8 也能硬上需要约 400MB 内存。我曾经在某数据分析脚本里就真用 10^8 的 int 数组做过一次计数统计明显比跑外部排序快得多——前提是这台机器内存够大脚本是短生命周期的。2.2 查找场景二分、哈希、还是直接数组下标查找问题里“范围已知”的价值被很多人低估了。当数据范围是有限的连续整数时最猛的查找结构其实是一个普通的数组。假设你有一个系统用户ID从 0 递增分配最多 10^7 个用户需要根据 ID 快速查到用户信息。此时直接开一个大小为 10^7 的数组下标就是 ID# 建立直接按下标存 users [None] * MAX_USER_ID def add_user(uid, info): users[uid] info def get_user(uid): return users[uid]查找复杂度为 O(1)而且没有任何哈希冲突、没有链表指针跳转、没有缓存缺失问题。相比之下哈希表虽然理论也是 O(1)但它需要计算哈希、处理冲突、可能触发扩容常数因子比数组直接定址大不少红黑树和跳表理论 O(log n)更是差了一个数量级。二分查找则适合另一种场景数据本身已经有序但你不知道数据的分布密度只知道范围。比如你要在一个已排序的数组中查找某个值二分查找完全不关心值域大小只关心元素个数 n这是它的天然优势。所以查找场景的决策逻辑大致如下值是连续或接近连续的整数且下界不大 → 直接数组定址值域稀疏但已知上下界 → 先离散化再用二分或哈希值域未知、数据静态有序 → 二分查找值域未知、数据动态插入删除 → 哈希表或平衡树。我不是说哈希表不好哈希表在很多场景确实是全能选手。但“范围已知”这个信息经常能把哈希表降级成一个更简单的数组省掉一堆隐形成本。尤其是高并发读取场景数组定址的局部性好CPU 缓存友好性能优势非常明显。2.3 去重场景位图与布尔数组的空间账去重问题的本质是“判断某个值是否出现过”。如果值的范围已知最简单的办法是布尔数组甚至位图。给一个具体例子。某系统需要过滤 10^9 条请求里的重复设备编号设备编号是 32 位非负整数最大值约 4×10^9——这个范围太大直接开 int 数组需要 16GB显然不现实。但如果换一个角度我们不关心某个编号出现了多少次只关心“是否出现过”就可以用位图来表示每个编号只占 1 bit4×10^9 个编号对应约 500MB。虽然也不小但已经比 int 数组省了 32 倍配合分段加载、多线程处理很多场景是可行的。如果范围再小一些比如设备编号实际是 MAC 地址后 24 位0 ~ 2^24-1约 1600 万个取值位图只需要 2MB。直接用 bitset 或手工字节数组都能轻松装进内存。// 位图去重假设值域为 [0, MAX_VAL) vectoruint8_t bitmap((MAX_VAL 7) / 8, 0); bool markIfFirstSeen(uint32_t val) { uint32_t byteIdx val 3; uint8_t bitMask 1 (val 7); bool first !(bitmap[byteIdx] bitMask); bitmap[byteIdx] | bitMask; return first; }哈希 Set 也能去重但它有两个问题内存占用大每个元素除了值本身还有哈希桶、节点指针、负载因子预留空间而且哈希碰撞后还会退化。所以当范围可控时位图在内存和时间上都是更优选择。去重场景的选型逻辑可以总结为值域 ≤ 10^7直接用布尔数组约 10MB值域 ≤ 10^9考虑位图约 125MB还是要评估内存预算值域 10^9 且实际元素数量少 → 哈希 Set 或布隆过滤器允许误判、且数据量极大 → 布隆过滤器它本质上也依赖“范围预估”来设定位数组大小和哈希函数个数。布隆过滤器这里尤其值得展开它需要的位数组大小依赖于你预估的元素数量 n 和可接受的误判率 p。公式是 m ≈ -(n × ln p) / (ln 2)^2。这不就是“根据已知数据范围预估规模选择参数”的典型例子吗范围估计得越准布隆过滤器就越省内存且误判可控。2.4 素数处理大范围区间筛的偏移存储技巧素数问题看起来和“数据范围选型”没直接关系但我做某次数论相关需求时踩过坑这里必须分享一下。如果需求是求区间 [L, R] 内的所有素数L 和 R 可能很大比如 L 10^9R 10^9 10^7。此时你没法直接开一个大小为 R1 的布尔数组来筛——那要 1GB 以上空间。但区间长度 R - L 1 只有 10^7是可以轻松放进内存的。做法是埃氏筛的“区间偏移”先用普通埃氏筛把不超过 sqrt(R) 的素数全部找出来再用这些素数去筛 [L, R] 区间内合数但数组下标只需要从 0 到 R-Lvectorbool isPrime(R - L 1, true); // 先用经典筛法得到所有 sqrt(R) 的素数 primes for (int p : primes) { // 找到 [L, R] 中第一个能被 p 整除的数 long long start max((long long)p * p, ((L p - 1) / p) * p); for (long long j start; j R; j p) { if (j ! p) isPrime[j - L] false; } }思路核心就是把值域范围从 [0, R] 偏移成 [0, R-L]也就是“已知区间长度而不是已知绝对最大值”。这类偏移技巧在算法竞赛和工程里都能见到本质上是让你不要被问题表面的大数值吓到——多问一句“我关心的范围到底是从哪到哪、跨度有多大”选型思路就会完全不一样。类似的还有线性筛欧拉筛它在需要频繁查询前缀素数个数、或需要维护每个数的最小质因子时更好用但代价是需要完整表。如果范围已知且不大比如 U ≤ 10^7线性筛是首选范围很大但只查某个区间区间筛配合偏移才是正解。3. 范围已知不等于一切稀疏、偏移、大值域的边界处理上一章讲的是“范围已知带来的红利”实际操作中更常见的却是“范围似乎知道了但没那么简单”。我把最常见的边界情况列一下。3.1 稀疏范围是陷阱值域大而实际元素少最常见的翻车场景是系统文档告诉你“编号范围是 1 到 10^9”于是你想开一个 10^9 的数组然后发现内存直接爆炸。但你仔细看看数据实际出现的编号总共只有 10^4 个——这就是稀疏范围。在稀疏范围面前直接定址不可行应该转向离散化把所有出现过的值收集起来排序去重后映射成 0 到 m-1 的紧凑下标再用数组或树状数组处理。比如你要对一堆区间做覆盖次数统计编号是 10^9 量级的离散点。开数组不可能但把这些点离散化后问题规模就变成“实际点数 m”所有基于范围下标的算法都能继续用vectorint allVals originalVals; sort(allVals.begin(), allVals.end()); allVals.erase(unique(allVals.begin(), allVals.end()), allVals.end()); // 之后要查某个 val先二分定位lower_bound(allVals.begin(), allVals.end(), val)这里“范围已知”的信息并没有失效而是换了一种用法范围决定了你能预判离散化后 m 的大小上限进而决定是选树状数组还是线段树、是选普通数组还是哈希。离散化后的查找用二分 O(log m)也可以再套哈希 O(1)如果 m 不超过 10^6甚至可以直接开一个大小为 m 的数组配合“反离散化映射”。我个人的经验是在做任何依赖“值域大小 U”的算法之前先统计“实际互异元素数量 m”。如果 m 远小于 U走离散化如果 m 和 U 同量级且 U 可控才考虑直接开数组。3.2 负数与起始偏移让下标从0开始的三种映射方式已知范围是从负数开始或者最小值远大于 0 时不能直接使用原始值作为数组下标。处理办法很简单建立从“原始值”到“数组下标”的映射常见有三种。第一种是整体平移。如果范围是 [-10^5, 10^5]把所有值加上 10^5变成 [0, 2×10^5]再开数组。这种方式最简单但前提是范围不大否则平移只是把问题延后内存照样过大。第二种是取模或哈希映射。适用于大值域但稀疏的情况本质上是哈希表不保证下标连续。第三种是排序后二分定位。也就是前面说的离散化适合值域范围大、但实际值集合固定且数量不多的查询场景。这三种方式的选型判断依据还是回到第一张表里那几个维度范围跨度、连续性、实际元素数量。如果跨度小且连续平移开数组最优跨度大且稀疏离散化加二分动态插入且无法排序哈希。一个我曾经忽略的细节做平移时一定要确认映射后的最大值不超过数组边界。比如值是 [10^6, 10^6 10^4]平移量是 10^6但有些人只平移了最小值却忘了数组长度等于“最大值减最小值加一”导致越界访问。测试时数据不靠边界根本发现不了一旦上线就偶发崩溃非常难排查。3.3 分布不均时基数排序比计数排序更稳计数排序在值域很小但分布极不均匀时有一个隐藏问题回填阶段需要把所有值域遍历一遍哪怕绝大多数值从来没有出现过。如果 U 10^8n 10^6那么 O(n U) 实际约等于 1.01 亿次操作大部分时间浪费在空转的 for 循环上。虽然也不算慢但内存开销已经不小400MB 左右的 int 数组。此时可以考虑基数排序的变体按二进制位分组做 LSD 排序。32 位整数按 8 位一桶只需 4 轮每轮 O(n)总共 O(4n)。它不要求值域连续只依赖于位宽。实测中当数据非常集中比如所有数都在 0 到 2^20 附近时基数排序依然稳定而计数排序则会因为 U 大而吃亏或者因为 U 小而先要扫描全范围。还有一个更实用的组合先根据高位做一次粗分桶把数据拆到若干个区间里区间内部如果值域跨度已经很小再对每个区间单独做计数排序。这种“桶排序 计数排序”的思路在很多大数据排序系统里都能见到本质就是利用数据范围的层次性——外层看范围分桶内层看区间跨度再细化。3.4 时间与内存的权衡bitset、压缩与分段处理当范围 U 很大但你又想保留“范围直接定址”的好处时内存会成为瓶颈。这时有几个工程手段值得掌握。位压缩前面提过值域 U 的布尔数组至少 U 字节位图只要 U/8 字节。例如 U 10^8布尔数组 100MB位图 12.5MB差距非常明显。分段处理如果一次性装不下可以考虑按值域分段。比如值域 0 到 10^9我把范围切成 100 段每段长度 10^7每次只加载一段到内存处理处理完写回结果再换下一段。这种方式牺牲了随机访问的便利性但能把“范围已知”的优势从内存受限场景中拯救出来。压缩编码当数据的值域连续但分布极不均匀时可以用差值编码、前缀和编码等方式压缩存储。这已经进入数据结构的深层定制了一般只在存储成本极高时才会考虑。我的建议是先别急着上压缩先用位图和分段扛一扛绝大多数场景已经够用。4. 从一次翻车经历谈选型前必问的六个问题讲完了原理我想用一段真实踩坑记录收尾。某次我负责一个内部统计系统需求是给海量请求按来源IP段聚合计数。IP是IPv4四个字节我当时想当然地以为“IPv4范围就是 0 到 2^32-1均匀分布”于是一开始就准备了一张大小为 2^32 的数组算一下 16GB直接超了内存预算。后来又改成哈希表但因为 IP 段极不均匀地集中在少数几个C段哈希表碰撞率很高性能又不行。最后我做了两件事先用采样统计出实际出现的IP段数量再把“IP地址范围”转换成“CIDR前缀范围”按前缀长度分层处理。最终方案是高频前缀用紧凑数组直接定址低频稀疏部分用离散化加二分。整体内存不到原来的十分之一性能还比哈希表快了三倍。这次经历让我总结出选型前必问的六个问题也推荐给你问题目的不回答的后果值的确定上下界是什么判断能否直接定址内存浪费或越界值域跨度多大实际出现多少互异值判断稀疏程度直接开数组爆内存值是连续还是离散分布是否均匀选择计数排序、基数排序还是桶排序空转/碰撞是否存在偏移、负数、大起始值决定是否平移/离散化下标越界是否需要稳定排序、随机访问、内存受限决定工程约束算法正确但工程不可用最坏情况下的值域边界是否可能突破预估决定是否留冗余上线后偶发崩溃这六个问题看着简单但真到项目里很多人是在写完代码之后才开始考虑的顺序反了。正确做法是写算法前先做 5 分钟的数据分析哪怕是粗略估算也远比凭感觉选结构要可靠。选完算法之后还有一步容易被漏掉用多组不同规模的数据做基准测试而不是只看理论复杂度。理论分析只告诉我们增长趋势常数因子、缓存行为、内存分配开销只有实测才能暴露。具体做法我一般是这样先把数据规模从小到大各测一轮比如 n 10^4、10^5、10^6、10^7同一规模下再测分布极不均匀的情况对比时间时顺带记录内存峰值如果理论曲线和实测曲线偏离超过一个数量级回头检查是不是忽略了对数项或线性扫描项。还是拿时间戳那个例子说。当时我把直接定址数组换成“哈希 红黑树”理论上排序和聚合看起来都严谨但实测下来数组版本因为缓存友好反而快了接近一个数量级。这个现象用大O符号很难解释但在真实硬件上就是那么残酷——常量因子、内存局部性往往比渐进复杂度更能决定一个系统的最终性能。而“范围已知”恰好能让你在更多场景里选择那个常量极小、局部性极好的数组方案。最后一个我个人的实操习惯在代码注释里把“为什么选这个算法”写下来。记录数据范围是多少、为什么认为范围可控、如果范围翻十倍应该怎么切换方案。这看起来像小事但对后来维护代码的人来说包括三个月后的自己这比写十行“这段代码实现了XXX”有用得多。算法选型不是一锤子买卖数据范围可能随着业务增长而变化那时就是重新评估算法的时候。以上就是我根据已知数据范围做算法选型的完整思路和实操经验。信息密度确实不低但如果你在真实项目中遇到确定值域的数据回来看一眼这六个问题应该能少走不少弯路。