首页 文章

具有与质数数量成比例的数据的主筛的空间复杂性是多少？

提问于
浏览 次
1

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

  • 这个理由有效吗？

  • 如何评估此算法的空间复杂度？

From Wikipedia about the sieve of Atkin - 我不确定的是，当素数超过此值时，筛子如何使用O（n ^ 1/2）空间 . 这就是为什么它似乎至少必须与质数的数量成比例 . 我是否将可数数字与空间复杂性混为一谈？

In this paper on the sieve of Atkin，他们的算法打印"the prime numbers up to N...Here “memory” does not include the paper used by the printer."这似乎是一个不公平的空间计算 .

  • 我希望澄清这应该如何/实际上客观地衡量 .
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
python primes space-complexity sieve sieve-of-atkin

3 回答

  • 1

    空间复杂度测量非常公平 . 如果用 yield n 替换 primes.append(n) ，并且在消费者例程中逐个处理素数而不将它们全部存储起来，例如为了找到具有特定属性的素数，则素数本身所需的存储空间为O（1），以素数计算 .

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

    回复于
  • 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和像How do i reduce the space complexity in Sieve of Eratosthenes to generate prime between a and b?这样的问题

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

    回复于
  • 1

    “使用优质筛子，至少你必须存储所有找到的素数列表 . ”

    不正确 . 您只需要在下限（包括）上限的平方根处填写素数，以筛选该范围内的素数 .

    如果您的筛子是增量的，无界限的，那么您只需要在当前 生产环境 点的平方根下面（并包括）填充 .

    怎么可能？通过为"core"素数（低于sqrt的素数）使用单独的素数供应，这是完全可以用相同的函数计算 - 递归 . 有关示例，请参阅this answer .

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

    而且，不能用它来击败Eratosthenes的正确轮式筛子（在_2422000_上搜索GordonBGood的答案，如this one） .

    回复于

相关问题