我正在进行Cracking the Coding Interview,我不确定时间复杂度的示例。他们提供此代码来确定一个数字是否是质数:
boolean isPrime(int n) {
for (int x = 2; x * x <= n; x++) {
if (n % x == 0) {
return false;
}
}
return true;
}
后来他们说“for循环内的功是常数”。为什么模运算符的运行时是常数?为什么它不依赖于n?
语句的关键部分在for循环内部。所有发生的都是模运算。在函数内部,时间复杂度取决于n