爲什麼找到一個具有指數時間複雜度的算法的因素？

據我所知，「模數」是一個按位運算符，它對單個位進行操作。因此，在最壞的情況下，我們需要執行sqrt（2^n）個分割。所以這是一個exp時間算法。

如果那是真的，是不是所有的算法都會變成指數時間？請解釋。

Find-Factor(X) 
1: if X is even then 
2: return 」2 is a factor」 
3: end if 
4: for i = 3 to Sqrt(X) by +2 do 
5: test if X%i = 0, if yes, output 」i is a factor」 
6: end for 
7: return 」X is a prime.」

來源

2014-09-01 Akash Deshpande

我不太明白第4行...... – HuStmpHrrr 2014-09-01 20:44:17

模塊是一個分區，而不是按位。只有當除數是2和文字的確切能力時，它纔會變成一個按位。 – 2014-09-01 20:45:16

@HuStmpHrrr請檢查。我已經改變了行 – 2014-09-01 20:53:06

指數性來自迭代次數。在最壞的情況下（這是案例編號是素數）你必須做X/2迭代（在這個算法中，它不是一個好的例子，例如你可以用sqrt（X）而不是X來限制循環）。這與輸入中的位數= ln（X）呈指數關係。不與數字X.

順便說一句，有概率檢查，確定給定的數字是否是質數或非常快。而且還有一個相當複雜的算法可以確定地完成相同的工作。你可以谷歌和找到他們。

來源

2014-09-01 20:46:42

一個投下來，你可以啓發我的理由嗎？有什麼不對？ – 2014-09-01 20:51:52

我更關心這是如何產生的。不是特別的素數算法。我想知道爲什麼2^n以及如何來這不適用於所有其他算法。 – 2014-09-01 20:55:21

這就是我，因爲「你必須做X/2循環」，而「來自循環數」。 – jthill 2014-09-01 20:57:36

他們在數字的表示的長度指數，因爲表示本身是指數，下一個數字是10 ^{N + 1}或2 ^{N + 1}或什麼的。線性搜索只是有更多的搜索，這就是全部。

來源

2014-09-01 20:50:57 jthill

表示本身是指數？這是什麼意思。你是指下一個素數的發生。 – crackerplace 2014-12-23 21:50:33

爲什麼找到一個具有指數時間複雜度的算法的因素？

回答

相關問題