爲什麼第二種解決方案比第一種更快？

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

請解釋爲什麼是第二個解決方案比第一批好。我在考試中提供了第一個解決方案，並且在解決方案效率不高的情況下，我的答案得到了回覆。我想知道什麼是大differene

Answer 1

所以這是一個測試的問題，我始終牢記一些教授有一個豐富多彩的特權，但我可以看到幾個原因之一可能聲稱的第一較慢：

• 當計算素數時，您只需測試是否有其他素數是因素。 第二所以種子奇數，3，然後增加了2次遞歸調用跳過檢查均等因素，並減少了一半所需的調用數量。

• 並且@uselpa指出，第二個代碼片斷在測試因子的平方大於n時停止。這個版本中的所有奇數在1和n之間已經被解釋了。這允許推斷n比首先第一個的質數快，其在宣佈質數之前一直計數到n。

• 可能會認爲由於第一測試爲遞歸函數，而不是像第二外方法內脣上，是它是在調用堆棧上的unnessary方法。

• 我似乎也有人聲稱三元操作比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?