1

我正在练习编写针对空间或时间复杂度进行优化的算法。使用素数筛，您至少必须存储找到的所有素数的列表。似乎与找到的素数成比例的数据是这种算法可能使用的最少空间。

  • 这个理由有效吗？
  • 如何评估该算法的空间复杂度？

来自关于阿特金筛子的维基百科- 我不确定当素数数量超过此值时，筛子如何使用 O(n^1/2) 空间。这就是为什么看起来至少空间必须与素数的数量成比例的原因。我是否将可数数字与空间复杂度混淆了？

在这篇关于 Atkin 筛子的论文中，他们的算法打印“最多为 N 的素数......这里的“内存”不包括打印机使用的纸张。” 这似乎是对空间的不公平计算。

  • 我希望澄清这应该如何/实际上是客观地衡量的。
def prime_sieve(limit):
    factors = dict()
    primes = []
    factors[4] = (2)
    primes.append(2)
    for n in range(3, limit + 1):
        if n not in factors:
            factors[n * 2] = (n)
            primes.append(n)
        else:
            prime = factors.get(n)
            m = n + prime
            while m in factors:
                m += prime
            factors[m] = (prime)
            del factors[n]
    return primes
4

3 回答 3

2

该算法的空间复杂度为len(numbers) + len(primes); 列表的大小加上字典的大小。

在这种情况下，该算法比您对简单素数筛 ( limit) 的预期差。len(numbers) + len(primes) > limit因为例如prime_sieve(100)以下不相关的数字存储在numbers：

{129: 43, 134: 67, 141: 47, 142: 71, 146: 73, 158: 79, 166: 83, 178: 89, 194: 97, 102: 17, 104: 2, 105: 3, 106: 53, 110: 11, 111: 37, 112: 7, 114: 19, 115: 23, 116: 29, 117: 13, 118: 59, 120: 5, 122: 61, 123: 41, 124: 31}

有几种质数筛，具有不同的时间和空间复杂度；参见例如Wikipedia和诸如如何降低埃拉托色尼筛中的空间复杂度以在 a 和 b 之间生成素数之类的问题？

另外，请注意不需要prime = numbers.get(n)- 你已经检查过if n not in numbers，所以你可以使用prime = numbers[n].

于 2014-10-20T10:15:29.753 回答
1

空间复杂度测量是完全公平的。如果您替换primes.append(n)为yield n，并且您在消费者例程中一个一个地处理素数而不将它们全部存储，例如查找具有特定属性的素数，则素数本身所需的存储空间为 O(1)，以素数的数量。

（yield是 Python 构造生成器的方式，生成器是一种向调用者发出值并保存函数状态以便可以重新输入的协程。）

于 2014-10-20T11:07:42.467 回答
1

" 使用素数筛，您至少必须存储找到的所有素数的列表。"

不正确。您只需要低于（包括）上限平方根的素数，即可筛选出该范围内的素数。

如果你的筛子是增量的、无界的，那么你只需要在当前生产点的平方根以下（包括）有素数。

这怎么可能？通过为“核心”素数（那些低于 sqrt 的素数）使用单独的素数供应，这完全可以用相同的函数计算 -递归。例如，请参阅此答案。

不计算产生的素数是完全合法的 - 你确实可以将它们发送到打印机或外部文件等。因此，这种筛子的空间复杂度将是O( sqrt(N)/log(N) ) ~ O( sqrt( n/log(n) ))n个素数，最多N ~= n * log n .

另外，不要靠近阿特金的筛子。街上的消息是，不可能用它来击败埃拉托色尼的适当轮式筛子（搜索GordonBGood关于这个主题的答案，比如这个）。

于 2014-10-20T21:25:34.603 回答