c++ - 这个素数测试函数的时间复杂度

Question

这个函数的时间复杂度是多少

bool prime(int n) {
    if(n <= 1) {
        return false;
    } else if(n <= 3) {
        return true;
    } else if(n % 2 == 0 || n % 3 == 0) {
        return false;
    } else {
        for(int i = 5; i * i <= n; i += 6) {
            if(n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
    }
    return true;
}

如果我不得不猜测，那将是

O(sqrt(log(n)))

Answer 1

每个 if 都是常数时间。

for循环执行直到i * i达到n这意味着它被执行了sqrt(n) / 6几次。所以复杂度是O(sqrt(n))。

它没有衡量素数的密度与1/log(n)（可能这是log(n)您的解决方案中的来源）成正比。

请注意，时间复杂度（无形容词）通常被认为是最差的时间复杂度：

时间复杂度 - 维基百科

由于算法的运行时间在相同大小的不同输入之间可能会有所不同，因此通常会考虑最坏情况时间复杂度，即给定大小的输入所需的最大时间量。不太常见且通常明确指定的是平均情况复杂度

在这种情况下，平均时间复杂度更难计算。您必须证明当n不是质数时循环平均终止的速度有多快。