algorithm - 将二次算法简化为线性时间

Question

我正在尝试编写一个在 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

Answer 1

您当前的方法以二次时间运行，因为对于序列 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