提问者:小点点

为什么模运算的时间复杂度是常数?


我正在进行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?


共1个答案

匿名用户

语句的关键部分在for循环内部。所有发生的都是模运算。在函数内部,时间复杂度取决于n