0

最初：

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);
}

2番目:

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);
}

2 番目のソリューションが最初のソリューションより優れている理由を説明してください。私は試験で最初の解決策を提示しましたが、その解決策は効率的ではないという主張に反論しました。大きな違いを知りたい

4

2 に答える 2

0

最初の解は、線形時間がかかるため O(n) の複雑さを持ちます。2 番目の解は、次のコード行により O(sqrt(n)) かかります。これif (div * div > n) return true;は、平方根を超える除数を探す必要がないためです。詳細については、次を確認してください。素数であるかどうかを判断するために、素数の平方根までチェックするのはなぜですか?

于 2016-03-03T12:40:20.400 に答える