检查素数 big-o

Question

我确定一个数是否为质数的原始函数是：

bool is_prime(int x) {
    for (int y = 2; y < x; ++y) {
        if (x % y == 0) {
            return false;
        }
    }
    return true;
}

这个运行的复杂度为 O(x)，因为您可能不得不去 x。

我了解了一些优化，需要检查一下我的 big-o。这是改进后的程序：

bool is_prime(int x)
{   
    if (x % 2  == 0 && x > 2) {
        return false;
    }
    for (int y = 3; y*y <= x; y += 2) {
        if (x % y == 0) {
            return false;
        }
    }
    return true;
}

我现在要升到 sqrt() 是否会更改为 O(sqrt(x))？

Answer 1

是的，但这里没有 n。新函数的复杂度为 O(sqrt(x))。当你说 O(N) 并且不指定 N 是什么时，它通常被认为是 size 的输入。这对于采用单个数字参数的函数来说是令人困惑的，因此在这些情况下你应该明确。

Answer 2

当然，你的新函数的复杂度是

O(sqrt(x))

不过，还有一些优化的空间。看看下面提到的代码：

bool isPrime(int n)
{
    // Boundary cases
    if (n <= 1)  return false;
    if (n <= 3)  return true;

    // This is checked so that we can skip 
    // middle five numbers in below loop
    if (n%2 == 0 || n%3 == 0) return false;

    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;

    return true;
}

检查素数 big-o

Check if prime big-o

c++

big-o

asymptotic-complexity