此素数测试函数的时间复杂度 [英] Time Complexity of this primality test function

问题描述

此功能的时间复杂度是什么

What would be the time complexity of this function

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;
}

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

If I had to guess, it would be

O(sqrt(log(n)))

推荐答案

每个时间都是固定时间.

Each if is constant time.

for 循环执行到 i * i 达到 n 为止，这意味着将执行 sqrt(n)/6 次.所以复杂度是 O(sqrt(n)).

for loop is executed until i * i reaches n this means it is executed sqrt(n) / 6 times. So complexity is O(sqrt(n)).

不能测量素数的密度与 1/log(n)成正比(可能这是解决方案中 log(n)的来源).

It doesn't meter that density of prime numbers is proportional to 1/log(n) (probably this is source of log(n) in your solution.

请注意，通常将时间复杂度(无形容词)视为最差的时间复杂度:

Note that time complexity (no adjective) usually is consider as worst time complexity:

时间复杂度-维基百科

由于算法的运行时间在相同大小的不同输入之间可能会有所不同，因此通常会考虑最坏情况的时间复杂度，它是给定大小的输入所需要的最大时间.平均情况复杂度

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 不是素数时，平均快循环会终止的情况.

Average time complexity is much harder to compute in this case. You would have to prove how fast loop terminates on average when n is not a prime number.

这篇关于此素数测试函数的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！