java - 我的 Java Sieve 代码速度很慢并且无法按预期的时间复杂度进行扩展

Question

我用 Java 编写了以下“分段筛”程序。它需要筛选一系列数字，使用“筛选素数”(素数数组列表变量)划掉复合数，然后返回尚未划掉的素数。这是代码:

public ArrayList<Integer> sieveWorker(int start, int last, ArrayList<Integer> primes) {

    System.out.println("Thread started for range: " + start + "-" + last);
    ArrayList<Integer> nonPrimes = new ArrayList<Integer>();
    ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
    ArrayList<Integer> numbers = new ArrayList<Integer>();

    //numbers to be sieved
    for (int i = start; i <= last; i += 2) {
        numbers.add(i);
    }

    //identifies composites of the sieving primes, then stores them in an arraylist
    for (int i = 0; i < primes.size(); i++) {

        int head = primes.get(i);

        if ((head * head) <= last) {
            if ((head * head) >= start) {
                for (int j = head * head; j <= last; j += head * 2) {
                    nonPrimes.add(j);
                }
            } else {
                int k = Math.round((start - head * head) / (2 * head));
                for (int j = (head * head) + (2 * k * head); j <= last; j += head * 2) {
                    nonPrimes.add(j);
                }
            }
        }

    }

    numbers.removeAll(nonPrimes);
    System.out.println("Primes: " + numbers);
    return numbers;
}

我的问题是它非常慢并且以 o(n^3) 的时间复杂度执行，而不是 o(n log log n) 的预期复杂度时间。我需要有关优化和纠正其时间复杂度的建议。

Answer 1

罪魁祸首是 numbers.removeAll(nonPrimes) 调用，对于 numbers 中的每个数字(并且有 O(n)他们)可能会搜索所有nonPrimes(其中有O(n log log last))来检查成员资格(以及nonPrimes也是未排序的)。 n 是数字的长度，n = 最后 - 开始。

因此，您不必对每个非素数进行 O(1) 标记，而是实际删除 O(n log log last)对于其中的每一个 O(n) 。因此，上面的操作总体上是O(n^2)。

克服这个问题的一种方法是使用简单数组，并标记非素数。删除会破坏直接寻址功能。如果要使用它，操作必须在线，每个数字接近O(1)次操作。这可以通过将非素数设置为排序列表，然后以线性方式从数字中删除它们来实现。这两项任务再次用数组最容易完成。