在哈希集中保留非素数与创建布尔数组之间的 space 和时间复杂度有何区别？
What is the difference in space and time complexity between keeping non-primes in a hashset vs. creating an array of Booleans?
我给定一个整数n，并告诉我return从1到n的所有素数
我知道这个问题已经在这里回答了很多次，但我的问题是围绕跟踪非素数的两种方法。这两种方法是：
创建一个array of size n，其中每个索引代表从1到n的数字，如果不是素数则用Boolean (i.e. True or False)标记每个条目； the array is initially empty，但是当我们遇到素数时，我们会将素数的所有倍数标记为 False（即不是素数）在我们的数组中，这样当我们得到数字时我们不需要 'check' 如果它是素数。否则，我们将 'check' 通过尝试从 0 到该数字的模数来判断该数字是否为质数。
创建一个 set() 并按照 1 从 0 迭代到 n。每次我们 运行 将其所有倍数存储在该集合中，并且对于从 0 到 n 的每一个数字，我们首先检查它是否在这个集合中，然后再测试它是否是素数。
上述两种方法在时间和Space复杂度方面有什么不同吗？
TLDR：从 big-Oh 的角度来看，它们在时间和 space 上都是等价的。然而，在实践中，存在显着差异。
时间复杂度：我们正在处理所有数字，在两种情况下都设置所有倍数 (N/2 + N/3 + N/5+ ...)。在这两种情况下，设置标志都需要 O(1) 时间。在这两种情况下，space 复杂度都是 O(n)。
区别在于，list 每个布尔值只占用几个字节。 Set 也使用相同的几个字节来存储值，但还必须存储密钥哈希、维护冲突记录和处理调整大小。虽然这一切仍然归结为渐近 O(1) 复杂度，但它在实践中有一个相当大的常量乘数。
我给定一个整数n，并告诉我return从1到n的所有素数
我知道这个问题已经在这里回答了很多次，但我的问题是围绕跟踪非素数的两种方法。这两种方法是：
创建一个
array of size n，其中每个索引代表从1到n的数字，如果不是素数则用Boolean (i.e. True or False)标记每个条目；the array is initially empty，但是当我们遇到素数时，我们会将素数的所有倍数标记为 False（即不是素数）在我们的数组中，这样当我们得到数字时我们不需要 'check' 如果它是素数。否则，我们将 'check' 通过尝试从 0 到该数字的模数来判断该数字是否为质数。创建一个
set()并按照 1 从 0 迭代到 n。每次我们 运行 将其所有倍数存储在该集合中，并且对于从 0 到 n 的每一个数字，我们首先检查它是否在这个集合中，然后再测试它是否是素数。
上述两种方法在时间和Space复杂度方面有什么不同吗？
TLDR：从 big-Oh 的角度来看，它们在时间和 space 上都是等价的。然而，在实践中，存在显着差异。
时间复杂度：我们正在处理所有数字，在两种情况下都设置所有倍数 (N/2 + N/3 + N/5+ ...)。在这两种情况下，设置标志都需要 O(1) 时间。在这两种情况下，space 复杂度都是 O(n)。
区别在于，list 每个布尔值只占用几个字节。 Set 也使用相同的几个字节来存储值，但还必须存储密钥哈希、维护冲突记录和处理调整大小。虽然这一切仍然归结为渐近 O(1) 复杂度，但它在实践中有一个相当大的常量乘数。