這個素數測試算法的時間複雜度？

我有下面的代碼，它確定一個數是否是素數：這個素數測試算法的時間複雜度？

public static boolean isPrime(int n){ 
    boolean answer = (n>1)? true: false; 

    for(int i = 2; i*i <= n; ++i) 
    { 
     System.out.printf("%d\n", i); 
     if(n%i == 0) 
     { 
      answer = false; 
      break; 
     } 
    } 
    return answer;  
}

我怎麼能確定這個功能的大O的時間複雜度？這種情況下輸入的大小是多少？

來源

2013-10-20 user2900638

想想這個函數的最壞情況運行時間，如果這個數字確實是質數，就會發生這種情況。在這種情況下，內部循環將盡可能多地執行。由於循環的每次迭代都會執行一定量的工作，因此完成的總工作量將爲O（循環迭代次數）。

那麼會有多少循環迭代？讓我們來看看循環邊界：

for(int i = 2; i*i <= n; ++i)

注意，這個循環將繼續執行，只要我 ≤ñ。因此，循環將立即終止，因此，循環將最終運行O（√ n）次，因此該函數的最壞情況時間複雜度爲O（√n）。

至於你的第二個問題 - 輸入的大小是多少？ - 通常，當查看素數測試算法（或其他大數量的算法）時，輸入的大小被定義爲寫出輸入所需的位數。在你的情況下，由於你的編號爲n，寫出n所需的位數是Θ（log n）。這意味着在這種情況下「多項式時間」可能類似於O（log ^k n）。運行時，O（√ n）時，不被認爲是多項式時間，因爲O（√ N）= O（（2- ^{爲log N}）^1/2），這是按指數比比特的寫出來所要求的數量較大輸入。

希望這會有所幫助！

來源

2013-10-20 21:32:42 templatetypedef

這個素數測試算法的時間複雜度？

回答

相關問題