gpt4 book ai didi

algorithm - Sieve of Eratosthenes 算法的时间复杂度

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:11:44 27 4
gpt4 key购买 nike

来自 Wikipedia:

The complexity of the algorithm is O(n(logn)(loglogn)) bit operations.

你是如何做到这一点的?

复杂性包括 loglogn 项告诉我某处有一个 sqrt(n)


假设我在前 100 个数字 (n = 100) 上运行筛选,假设将数字标记为组合需要常数时间(数组实现),我们使用 的次数>mark_composite() 会像

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

而要找到下一个素数(例如在划掉所有 5 的倍数后跳转到 7),操作次数为O(n)

因此,复杂度为 O(n^3)你同意吗?

最佳答案

  1. 您的 n/2 + n/3 + n/5 + … n/97 不是 O(n),因为项数不是常数。 [编辑后编辑:O(n2) 的上限太宽松。] 宽松的上限是 n(1+1/2+1/3+1/4+1/5+1/6+…1/n)(所有 数的倒数之和,直到 n),即 O(n log n):参见 Harmonic number .更合适的上限是 n(1/2 + 1/3 + 1/5 + 1/7 + …),即直到 n 的素数的倒数之和,即 O(n log log n)。 (参见 herehere。)

  2. “找到下一个质数”位总体上只有 O(n),amortized — 您将继续前进以在总计 中查找下一个数字 n 次,而不是每一步。所以整个算法部分只需要 O(n)。

所以使用这两个你得到 O(n log log n) + O(n) = O(n log log n) 算术运算的上限。如果你计算位操作,因为你正在处理最多 n 的数字,它们大约有 log n 位,这是 log n 的因子进来的地方,给出 O(n log n log log n) 位操作。

关于algorithm - Sieve of Eratosthenes 算法的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2582732/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com