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

每个时间都是固定的时间。
执行for循环，直到i * i达到n，这意味着已执行sqrt(n) / 6次。因此，复杂性就是O(sqrt(n))。
不能测量素数的密度与1/log(n)成正比(可能这是解决方案中log(n)的来源。
请注意，通常将时间复杂度(无形容词)视为最差的时间复杂度:
Time complexity - Wikipedia

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity

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