檢查黃金大O

我原來的功能，以確定是否一個數主要是：檢查黃金大O

bool is_prime(int x) { 
    for (int y = 2; y < x; ++y) { 
     if (x % y == 0) { 
      return false; 
     } 
    } 
    return true; 
}

這跑了的O(x)複雜，因爲你可能不得不去x。

我已經學會了一些優化，需要檢查我的big-o。下面是改進方案：

bool is_prime(int x) 
{ 
    if (x % 2 == 0 && x > 2) { 
     return false; 
    } 
    for (int y = 3; y*y <= x; y += 2) { 
     if (x % y == 0) { 
      return false; 
     } 
    } 
    return true; 
}

的，這對我現在馬上要到sqrt()更改爲O(sqrt(x))？

來源

2017-08-12 datta

@MattTimmermans同意你和AndyG的建議。我用'x'編寫函數，所以它應該是'x'而不是'n'。 – datta

另一個優化是預先計算'x'的整數平方根（即找到一個整數'm'，這樣'm * m'在正數'x'的'x-1'和'x'之間）。有效的算法（複雜性O（log（x））或更好）用於計算整數平方根，而不訴諸於浮點。 – Peter

@Peter我原本沒有進行浮點數轉換，但數學表明'm * m'在這裏可以達到目的。 – datta

是的，但這裏沒有n s。新功能的複雜性爲O（sqrt（x））。當你說O（N）並且沒有指定什麼N是，它通常被認爲是輸入的大小。這對於採用單個數字參數的函數來說很混亂，所以在這些情況下，您應該明確。

來源

2017-08-12 23:16:07

當然，新功能的複雜性是

O（開方（X））

但儘管如此，有一些優化的餘地。看看下面提到的代碼：

bool isPrime(int n) 
{ 
    // Boundary cases 
    if (n <= 1) return false; 
    if (n <= 3) return true; 

    // This is checked so that we can skip 
    // middle five numbers in below loop 
    if (n%2 == 0 || n%3 == 0) return false; 

    for (int i=5; i*i<=n; i=i+6) 
     if (n%i == 0 || n%(i+2) == 0) 
      return false; 

    return true; 
}

來源

2017-08-13 02:44:08

回答

相關問題