问题描述
此功能的时间复杂度是什么
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:
在这种情况下,平均时间复杂度很难计算.您必须证明 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.
这篇关于此素数测试函数的时间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!