以这样的方式填充数组,使得每个元素等于两个数的最小总和

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)

问题:还有其他方法可以更快地完成这项工作吗？
我正在寻找能够找到每个a _i的值小于O(n)的任何数据结构或算法.

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

Answer 1

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

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