最壞情況分析在循環

所以我寫了這個循環，但我無法分析其最壞情況的時間複雜性。任何幫助將不勝感激。最壞情況分析在循環

因素是任意數量的 primeNumber是素數2之間的名單和要素的原始值

for (int i = 0; i < primeNumbers.size() - 1; i++) { 
    prime = primeNumbers.get(i); 
    if(prime<=factor) { 
     if (factor % prime == 0) { 
      factor = factor/prime; 
      divisors.add(prime); 
      i = 0; 
     } 
     if (factor <= 3) 
      break; 
    } 
    else 
     break; 
}

來源

2014-04-21 calixProg

什麼是因素？它在哪裏定義？ – Mureinik

那麼，假設'primeNumbers'具有任意大小的'n'，最多可以運行多少次？ – Bucket

只是修改了它並添加了更多信息，並且我試圖查看最多可以運行多少次 – calixProg

最壞的情況：因素是素數。
所以我們永遠不會去break指令。
循環體將執行primeNumbers.size()次。

現在我們應該評估primeNumbers.size()。
它是number of prime numbers below a given number = O(n/ln n)。

讓我們證明獲得if (factor % prime == 0)語句會減少計算次數。
如果我們到達那裏，那就意味着factor = p*m。
所以我們會得到O(p/ln(p) + m/ln(m)) = O((p*ln(m) + m/ln(p))/(ln(m)*ln(p))) < O((p*m)/(ln(m)*ln(p))) < O((p*m)/(ln(m) + ln(p))) = O(p*m/ln(m*p)) = O(n/ln n)。
這樣劃分我們減少了計算次數。

來源

2014-04-21 16:09:19 Nikolay

您是否考慮過如果因素％prime == 0我們將計數器重置爲0並重新啓動，但使用不同的因子 – calixProg

好點。這只是直覺，劃分只會減少計算量。我爲這個案子增加了正式的證明。 – Nikolay

哦，哇，你真的很擅長這個..哈哈，這對我很有意義，現在非常感謝尼古拉 – calixProg

尼古拉的迴應給出了你所問的問題的最直接的回答，這個問題是關於分工操作數量方面的性能複雜性，假設每個分工操作具有統一的成本。然而，有兩個觀察結果：

1）通過停止循環，只要prime^2>因子可以顯着提高此測試的性能。這是因爲如果在因子的平方根以下沒有找到除數，那麼也不會在平方根以上找到一個。通過此修改，您將獲得O（sqrt（n）/ ln（sqrt（n）））= O（sqrt（n）/（sqrt（n）/ 2））= O（sqrt（n）/LN（N））。

2）在數字變得足夠大以致「有趣」（即不能被放入64位整數但可以任意大的數字）的地方，您的方法將面臨一個有趣的問題：查找第n個項目的操作將會增加，因爲在目前大多數硬件上，您可能會遇到所有素數的內存管理問題。你可能仍然可以把所有素數都適合32位整數，因此可以發現所有整數小於64的因素，但除此之外，你的方法將面臨明顯的麻煩。在任何情況下，一旦超過64位並開始尋找諸如Java BigInteger之類的任意大整數的因子，即使您可以管理內存，性能分析也需要更新以考慮實際整數的大小正在考慮。尼古拉的分析是好的，假設每個部門都有統一的成本。但是如果你開始處理更大數量的表示，統一成本的假設就被打破了。

來源

2014-04-22 04:36:55

最壞情況分析在循環

回答

相關問題