查找素数高达X - 复杂度

-2

该算法需要制作一个大小为X的数组，然后每个数字在其索引中不是主要输出零。有人可以告诉我什么是复杂性吗？为什么？查找素数高达X - 复杂度

// x is the number we want all the primes below him 
    int[] p = new int[x + 1]; 

    // Initializes the array. 
    for (int i = 2; i < p.length; i++) { 
     p[i] = i; 
    } 

    // "Erases" the composite (non-prime) numbers. 
    for (int i = 2; i <= Math.sqrt(x); i++) { 
     for (int j = i * 2; j < p.length; j += i) { 
      p[j] = 0; 
     } 
    }

是复杂度为O（X *的sqrt（x））？

来源

2013-06-12 tubu13

阅读Erastothenes筛上的维基百科页面。 –

您应该将j的定义更改为j = i * i。一旦你这样做，复杂性就是O（x log log x）。 – user448810

@ user448810对不起，这是不正确的。无论我们从'j = i * i'还是'j = i * 2'开始“擦除”，复杂度都是相同的，*对于随机访问集合中的'O（1）'update *，我假设Java数组是。 –

如果您使用以下代码，则时间复杂度为O（x √ x）。

int[] p = new int[x]; 
for (int i = 0; i < p.length; i++) { 
    p[i] = i+1; 
} 
for (int i = 4; i <= p.length; i++) { 
    for(int j = 2; j <= Math.sqrt(i) ; j += 1) { 
     if(i%j==0) { 
      p[i-1] = 0; 
     } 
    } 
}

来源

2013-06-13 05:21:39 Deepu

查找素数高达X - 复杂度

回答

相关问题