将二次算法减少为线性时间

我正试图编写一个在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我不同意你。逐项累加总和原则上与以总和开始和逐个减去相同。我在这里错过了什么吗？ –

浮点运算不准确。有四舍五入。误差随着项数的增加而线性增长。 –

将二次算法减少为线性时间

回答

相关问题