素因子分解算法的效率

-1

我想了解創建有效的素因子分解算法的問題是什麼。具體來說，我迄今爲止所做的研究表明，目前還沒有發現能找到O（n爲）時間的主要因素的算法。然而，顯而易見的算法對我來說是一樣的東西（僞）素因子分解算法的效率

method(int number, ArrayList<int> listOfPrimes) 
{ 
    int x = 0; 
    for (int i : listOfPrimes) 
    { 
     for (int j : listOfPrimes) 
     { 
     if (i * j = number) 
      { 
      x = i*j; 
      } 
     } 
     } 
    return x; 
}

我覺得method是O（n ），其中n是列表的大小。顯然，我對這個問題的理解是有缺陷的，或者不會有關於素因素化的大驚小怪。我哪裏錯了？

來源

2017-09-04 Jonnie Marbles

是的那就是O（n^2）。 –

你怎麼生成listOfPrimes？ – marvel308

你可能想問[math.se]，因爲它與編程沒有直接關係。 –

更加理想的方式是

method(int number, ArrayList<int> listOfPrimes) 
{ 
    int x = 0; 
    for (int i : listOfPrimes) 
    { 
     while(number%i == 0){ 
      number /= i; 
      x++; 
     } 

    } 
    return x; 
}

這個返回一個數字的計數首要因素。複雜性是

爲O（n + number_of_prime_factors）

其中n是listOfPrimes

來源

2017-09-04 12:09:09 marvel308

因此，我誤解了多項式時間是什麼？或者還有其他一些因素會使主因式分解變得困難嗎？ –

這是假設生成listOfPrimes，生成這將是主要的頭痛 – marvel308

此外，複雜性會少得多，因爲內部while循環將只運行素數因子次數 – marvel308

正如@dmuir提到的長度，你的「n」是不正確的「N 」。否則一個微不足道的O（n）的算法，以因子將是：

factor(n){ 
    for (int i=2; i<n; i++) { 
     if (n % i == 0) { 
     print("found factor:", i); 
     return i; 
     } 
    } 
}

對於理，輸入的大小位數被測量，所以「n」是在數位數或比特數。最好的算法有一個非常複雜的複雜度，需要一些數論理解，但是「大於」多項式時間卻「小於」指數時間，其中引用的短語可以形式化。出於這個原因，複雜性有時被稱爲「subexponential」。

來源

2017-09-04 13:47:40

素因子分解算法的效率

回答

相關問題