<分区>
这个算法的时间复杂度是多少？
void prime(int n) {
int i = 2;
while ((n % i) && i <= sqrt(n))
i++;
if (i > sqrt(n))
print(“%d is a prime number\n”, n);
else
print(“%d is not a prime number\n”, n);
}
<分区>
这个算法的时间复杂度是多少？
void prime(int n) {
int i = 2;
while ((n % i) && i <= sqrt(n))
i++;
if (i > sqrt(n))
print(“%d is a prime number\n”, n);
else
print(“%d is not a prime number\n”, n);
}
最佳答案
复杂度大约为 O(sqrt(N))。有些书会将其表示为 O(N0.5)。
每次循环迭代都会重新计算平方根。这是一个相当慢的操作，所以它比最优的要慢，但只是一个常数因子，所以它不会影响计算的复杂性。
关于c++ - 这个算法的复杂度是多少，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39461515/