我們在我的班級中介紹了 P 類，這一部分讓我感到困惑，因為素性問題是否在 P 中
我們的計劃：
"{prime(x): i =2; while i < x { if n mod i == 0 { return 0 } i } return 1 }"
程式的復雜性：如果 x 是 n 位長，那么 x 大約在 10^n 附近。（假設沒有前導 0，10^n?1 ≤ x < 10^n。）你在小學學到的除法演算法在 O(mn) 時間內將一個 m 位數字除以一個 n 位數字。綜上所述，我們發現測驗一個整數是否為素數的演算法需要時間 O(n^2 10^n)。
我的問題：教授在世界上哪里得到 x 是 10^n，例如，如果 x 是 17，它如何變成 x 是 10^2 = 100 次操作長。此外，最后一個大 O 符號中的 n^2 來自哪里。
uj5u.com熱心網友回復：
當 x 是素數時，這個試除演算法必須嘗試 x?2 個除數（即其中的 Θ(10 n )）。這些除數中的絕大多數有 n 或 n-1 位數字，因此每個除法平均需要 Θ(n 2 ) 時間，因為 m = Θ(n)。
uj5u.com熱心網友回復：
"{prime(x): i =2; while i < x { if n mod i == 0 { return 0 } i } return 1 }"
我的意思是n你的意思x，所以你的代碼應該看起來像
prime(x){
if(x == 2) return 0;
for(int i = 2; i < x; i )
if(x mod i == 0) return 0
return 1
}
該演算法是最簡單的解決方案，其成本為 O(x)。
它測驗從 2 到 x 的所有自然數。假設模數是一個常數時間運算，您將執行 x - 1 次運算（在最壞的情況下），因此 O(x - 1) = O(x)。
顯然有更好的解決方案，例如評估篩子以預先計算素數，這樣您就不需要為每個其他自然數除以 x。
uj5u.com熱心網友回復：
教授在世界上哪里得到 x 是 10^n
他們沒有。
他們說的其實是：
如果 x 是 n 位長，那么 x大約在10^n附近
在你的情況下，它下降了 100/17≈5.9。但這是一個不變的因素（而不是一個大的因素）。在最壞的情況下，它下降了 10 倍。在復雜性類別中，我們忽略了這些常數因子，因此它們的分析無關緊要。
uj5u.com熱心網友回復：
那么，素性問題是P，看到AKS測驗的詳細資訊
然而，天真的演算法（也就是在這個問題）是不是在P。鑒于x我們有
時間復雜度t = O(x)：
{prime(x):
i = 2;
while i < x { # we loop x - 2 times, t = O(x)
if n mod i == 0 {
return 0
}
i
}
return 1
}
問題的大小s = O(log(x))- 我們必須提供所有數字來寫x：
x = 123456789 # size is not 123456789, but 27 bits (or 9 digits)
所以時間復雜度t從大小的問題s是O(2^s)，如果大小s是位或者O(10^s)如果尺寸s是十進制數字。那絕對不是多項式。
讓我們看看你的例子：如果x是n數字長（log10(x)），t將是~ 10^n：
x : size (digits) : time
----------------------------------------------------
17 : 1.23 : 15 # your example
~ 17_000_000_000 : 10.23 : ~ 17_000_000_000 # just 10 times longer
你time ~ f(size)現在能看到指數嗎？
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359120.html