筛法求素数时用Boolean数组和set存非素数的时空复杂度差异

结论先行 #

两种方案的渐近时间复杂度、渐近空间复杂度完全一致，但实际运行效率、实际空间占用存在明显差距。 #

详细分析 #

时间复杂度部分 #

• 渐近维度：两种方案核心都是埃拉托斯特尼筛法的逻辑，总标记操作次数和埃氏筛完全对齐，渐近时间复杂度均为 O(n log log n)，没有差异。
• 实际运行效率差异：
  • 布尔数组的下标访问、标记操作都是底层直接内存寻址，常数开销极低。
  • 哈希set()的插入、存在性校验虽然平均时间复杂度也是O(1)，但需要额外承担哈希计算、哈希冲突校验/解决的开销，实际运行速度远慢于数组实现。
  • 两种方案里「未标记则执行模运算判断素数」的逻辑完全一致，不会带来额外的复杂度差异。

空间复杂度部分 #

• 渐近维度：数组方案固定申请大小为n的布尔空间，set方案最多存储O(n)个非素数元素，二者渐近空间复杂度均为 O(n)，没有差异。
• 实际空间占用差异：
  • 布尔数组的每个标记位仅占用1比特（部分语言实现为1字节），空间利用率极高，比如n=1e7时仅需1MB到10MB左右的空间。
  • 哈希set()需要存储每个非素数的完整整数值，还要承担哈希表的额外 overhead（包括预留空位、链表/红黑树节点开销等），相同n下空间占用通常是布尔数组的10倍以上。

内容的提问来源于stack exchange，提问作者Patrick_Chong