Java 中这个 PrimeNumbers 算法的时间复杂度

Question

我是时间复杂度分析的新手...

如果有人能告诉我这是否是二次的，我将不胜感激。而且如果有更简单的方法可以使它成为o(1)。

public class PrimeNumbers {
    public boolean isPrime(int n) {
        boolean retValue = true;
        for (int i = 2; i < n; i++) {
            if (n % 2 == 0) {
                retValue = false;
            }
        }
        return retValue;
    }
}

如果有人可以分解它为什么是这样，它肯定会帮助我学习。:)

非常感谢！

Answer 1

该算法的最坏情况运行时间为 O(n)。您的算法通过从 2 到 n 进行计数（因此循环运行 O(n) 次）并在每一步执行一些算术运算（每个都在 O(1) 时间内运行）。因此，整体运行时间为 O(n)。

您可以通过几种方式加快速度。一种方法是只计算 √n 而不是 n 本身，因为如果 n 有任何因数，那么这些因数中至少有一个是素数。有一个很酷的事实，即数字 n 的任何质数除数都不能大于 √n，因此您只需要数到 √n，包括 √n。这将您的运行时间降低到 O(√n)，这是一个显着的改进。

您可以使用其他算法来进一步加快速度，但它们非常复杂，并且仅对非常非常大的整数才真正有用。

您已经询问过将其归结为时间 O(1)。由于只有有限多个可能的值可以放入int，因此一种选择是构建一个包含所有适合于 的素数的巨型表int，将它们存储在哈希表中，然后在其中查找有问题的数字桌子。它并不优雅，而且占用大量内存，但它会起作用。

根据您的用例，您可能还想查看 Eratosthenes 的筛子，它将为您提供一种计算所有质数的方法，直到时间为 O(n) 的某个数 n，然后给出 O(1) 查询该范围内的任何数字。

希望这可以帮助！