6.2.2 筛法 (Sieving)：空间换时间的策略

文档摘要

6.2.2 筛法 (Sieving)：空间换时间的策略在算法设计的幽深峡谷中，有一类问题如顽石般横亘于我们面前：它们的答案确凿存在，却仿佛被锁在时间与空间的双重牢笼里——穷举所有可能解需要指数级的时间，而存储中间状态又轻易突破内存边界。当回溯、分支限界、动态规划在某些实例上步履蹒跚时，一种古老却锋利的策略悄然浮现：筛法（Sieving）。它不追求“边算边判”的即时性，而是以预分配、批量标记、空间冗余为代价，换取单次查询的常数响应与整体枚举的线性加速。这不是妥协，而是一种战略性的资源重配；不是退让，而是将计算的洪流引向更宽阔的河床。你或许熟悉埃拉托斯特尼筛法——那个在小学奥数课本里用划掉合数来留下质数的朴素图景。