c++ - 以每个元素等于两个数字的最小和的方式填充数组，使得

Question

给定一个数组(仅包含 正数 整数)已经有前 k 个元素:a₁, a₂, .... a_k。
我需要填充剩余的 (n - k) 元素(数组总共有 n 元素)。
n 的值约为 10 ^ 3 和 1 <= k <= n。
每个 a_i 的值是两个数字的最小和，使得这两个数字的位置之和等于 i。

这是伪代码(我的算法):

for i = k + 1 to n
  a[i] = max_value
  for j = 1 to (i / 2)
    a[i] = min(a[i], a[j] + a[i - j])

时间复杂度:O(n^2)

问题:有没有其他方法可以更快地做到这一点？
我正在寻找可以在小于 O(n) 的时间内找到每个 a_i 的值的任何数据结构或算法。

P/S:这是我程序中的一个过程，所以我需要尽快完成。

Answer 1

您可以通过使用线程并行运行最小值检查来提高程序速度。例如，您可以运行 4 个线程，每个线程检查 j 范围的 1/4。这将略微提高速度，但您的算法仍将花费 O(n^2) 运行时间。

我同意您很可能无法超越 O(n^2) 的评论。所以你最好的选择可能是尝试这样的事情来优化你的代码以减少 n^2 前面的系数。