複雜性這一素數搜索算法的

所以我目前瞭解大O符號，我不知道如何工作了大O是我下面的（故意低效率）的算法是什麼：複雜性這一素數搜索算法的

def getPrimes(n): 

primes = [2]  

for i in range(3, n+1): 
    remainder = True 
    for j in primes: 
     if(i % j == 0): 
      remainder = False 
    if(remainder == True): 
     primes.append(i) 
return primes

內循環運行的次數將增加，取決於列表內有多少項目「素數」。那麼，如何影響制定大O的目標呢？

來源

2014-11-23 Adam

檢查Pi(n) function。近似值是n/ln（n）。
整體算法（一種Eratosthenes實現的篩選）複雜度is evaluated as O(n(loglog(n))

來源

2014-11-23 19:12:53 MBo

給出的算法效率不高，因爲它測試每個素數對每個素數的篩選。我認爲這樣做效率不夠，無法將其推向更復雜的階層。 – 2014-11-24 01:49:09

每個我都針對所有素數小於i的測試。因此，完成的工作總量爲：

sum(i=3..n)pi(i)

（其中pi（i）是小於i的素數）。

PI（n）是西塔（N/log n）的，所以完成工作的數量是相同的複雜類爲：

sum(i=3..n)i/log(i)

我不認爲有任何好的近似這一點，但它比O（n^2）要好，但由於log（i）與i相比增長緩慢，所以不會太多。

來源

2014-11-24 01:46:30

複雜性這一素數搜索算法的

回答

相關問題