將二次算法減少爲線性時間

我正試圖編寫一個在O（n）時間內運行的算法。本質上，它需要一個整數n並將一個和乘以一個係數。然而，我寫這個算法的第一次嘗試運行時間爲O（n^2）。（見下文）有什麼辦法可以減少運行時間？將二次算法減少爲線性時間

for i = 1 to n 
    num1 = i/n 
    num2 = 0 
    for j = i to n-1 
     num2 = num2 + 1/j 
    result[i] = num1 * num2

來源

2015-10-15 user5447722

計算'我'下來。增量更新'num2'。 –

您當前的做法是在二次時間運行，因爲，對於序列中的每個元素1..n您再次遍歷序列。您可以刪除額外的工作，因爲您僅需要計算num2總和一次。在此之後，它可以被重用。

num2 = 0 
for j = 1 to n-1 
    num2 = num2 + 1/j 

for i = 1 to n 
    num1 = i/n 
    if (i > 1) 
     num2 = num2 - 1/(i-1) // reuse the summation by subtracting 
    result[i] = num1 * num2  // off the portion you don't want for this value of i

來源

2015-10-15 03:34:44

我低估了這個解決方案，因爲由於截斷誤差的原因，解析不會非常精確。 @DavidEisenstat的建議更好。 –

@Yves我不同意你。逐項累加總和原則上與以總和開始和逐個減去相同。我在這裏錯過了什麼嗎？ –

浮點運算不準確。有四捨五入。誤差隨着項數的增加而線性增長。 –

將二次算法減少爲線性時間

回答

相關問題