为什么第二个解决方案比第一个快？

Question

第一个:

boolean isPrime(int n) {
    if (n < 2)
        return false;
    return isPrime(n, 2);
}

private boolean isPrime(int n, int i) {
    if (i == n)
        return true;
    return (n % i == 0) ? false : isPrime(n, i + 1);
}

第二:

boolean isPrime(int n) {
    if (n < 0) n = -n;
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    return rec_isPrime(n, 3);
}

boolean rec_isPrime(int n, int div) {
    if (div * div > n) return true;
    if (n % div == 0) return false;
    return rec_isPrime(n, div + 2);
}

请解释为什么第二种解决方案比第一种更好。我在考试中提供了第一个解决方案，但我的足尖因声称该解决方案无效而被取消。我想知道最大的不同是什么

Answer 1

所以这是一个测试问题，我始终牢记一些教授有丰富多彩的特权，但我可以看到一些人可能会声称 first 较慢的原因：

在计算质数时，您实际上只需要测试另一个质数是否是因数。 second so seeds with odd, 3, then adds 2 ever recursive call which skips checking evens factors and decreases the numbers of calls needed by half.
正如@uselpa 指出的那样，second 代码片段在测试因子的平方大于 n 时停止。这实际上意味着在这个版本中，1 和 n 之间的所有奇数都已被考虑在内。这允许比 first 更快地推断 n 是素数，后者在声明素数之前一直计数到 n。
可能会争辩说，由于 first 在递归函数内部测试偶数，而不是像 second[=33= 这样的外部方法], 它是否是调用堆栈上的一个不必要的方法。

我似乎也有一些人声称三元运算比 if-else 检查慢，所以您教授可能会陷入这种信念。 [就个人而言，我不相信存在性能差异。]

希望这对您有所帮助。考虑一些质数很有趣！

Answer 2

第一个解决方案的复杂度为 O(n)，因为它需要线性时间，第二个解决方案需要 O(sqrt(n))，因为这行代码：if (div * div > n) return true;，因为要寻找不需要超过平方根的除数。有关详细信息，您可以查看：Why do we check up to the square root of a prime number to determine if it is prime?

为什么第二个解决方案比第一个快？

Why is the second solution faster than the first?

recursion

time-complexity

code-complexity