Eratosthenes算法的筛选时间复杂度

  • Z时代
  • 2024-01-10
  • 分类：问答

从维基百科：

该算法的复杂性是 O(n(logn)(loglogn))位运算。

包含loglogn术语的复杂性告诉我在sqrt(n)某个地方。

假设我在前100个数字（n =100）上运行筛子，假设将数字标记为复合数字需要固定的时间（数组实现），那么我们使用的次数mark_composite()将类似于

n/2 + n/3 + n/5 + n/7 + ... + n/97        =      O(n^2)

并且要查找下一个质数（例如，7在除掉所有倍数为的数字后跳至5），操作数将为O(n)。

因此，复杂度为O(n^3)。

回答：

  1. 您的n / 2 + n / 3 + n / 5 +…n / 97不是O（n），因为项数不是常数。[编辑后编辑：O（n 2）的上限太宽松。]宽松的上限是n（1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 +… 1 / n）（不超过n 的 所有 数字的倒数之和），即O（n log n）：请参见谐波数。一个更合适的上限是n（1/2 + 1/3 + 1/5 + 1/7 +…），即最高达n的质数的倒数之和，即O（n log log n）。（请参阅此处或此处。）

  2. 总的来说，“查找下一个质数”位仅O（n），摊销后 –您将向前查找 仅n次的下一个数，而不是逐步查找。因此，算法的整个部分仅需O（n）。

因此，使用这两个，可以得到O（n log log n）+ O（n）= O（n log logn）算术运算的上限。如果您对位运算进行计数，则由于您要处理的数字最多为n，因此它们大约有log n位，这就是log n的因数，给出了O（n log nlog log n）位运算。

以上是 Eratosthenes算法的筛选时间复杂度 的全部内容， 来源链接： utcz.com/qa/402816.html

回到顶部