以最小的总和填充数组，使得每个元素等于两个数字的最小总和

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的值。

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

- enofwiz

---

如果这是真正的代码，你真正想做什么？看起来像是一个 XY 问题。 - C. K. Young

我添加了描述，这是我的代码（直截了当的） - enofwiz

我看了你的编辑。你的问题仍然太抽象了。你的代码试图解决什么实际问题？ - C. K. Young

也许与本题无关，但如果您将操作+替换为*，并将min替换为+，并且还有a1 = a2 = 1（并且您正在寻找a3,...），您最终会得到卡特兰数列 。在这种情况下，您可以得到包括卷积的递归关系式，因此可以使用生成函数得到闭合形式解。不幸的是，所有这些在您的问题中都不可能。 - iavr

@ColonelPanic：例如：我们有 a1 = 10，a2 = 6，a3 = 4，需要计算 a4，a5 等等。以下是计算过程：a4 = min(a1 + a3, a2 + a2) = 12；a5 = min(a1 + a4, a2 + a3) = 10；a6 = min(a1 + a5, a2 + a4, a3 + a3) = 8......以此类推。 - enofwiz

Answer 1

想法 1

据我所知，这不会对 O(n^2) 的时间复杂度带来保证性的改进，但实际上它应该能够大大减少内部循环的次数。基本思路是我们可以以一种不同的顺序在内部循环中测试成对元素，这样我们就可以在很多情况下提前结束循环。具体来说，我们首先将数字的位置排序并存储在 s[] 中，使得 a[s[i]] 是 a[] 中第 i 小的数字。然后在主要的内部循环中，我们按照第一个项递增的顺序使用 a[s[j]]（而不是 a[j]）和 a[i - s[j]]（而不是 a[i - j]）来形成成对和。这给了我们两种方法来提前结束内部循环：

1. 如果 a[s[j]] >= a[i]，那么我们可以停止了，因为每个后面的和都必须更大，因为它们中的每一个的第一项（a[s[j+1]]等）必须至少与到目前为止最佳解（已在a[i]中）一样大，并且另一项永远不可能是负数。
2. 如果 a[i - s[j]] <= a[s[j]]（也就是说，如果下一个最小数的“伴侣”小于或等于它），我们可以停止，原因更加复杂。假设相反，后面有一些更好的对和 a[s[m]] + a[i - s[m]]（即 m > j）。我们知道第一项 a[s[m]] 必须至少与当前第一项 a[s[j]] 一样大，因为我们按递增顺序访问第一项，而 m > j；因此，对于对和 a[s[m]] + a[i - s[m]] 更好（即更小）的情况，它的第二项 a[i - s[m]] 必须小于我们当前的第二项 a[i - s[j]]。 （这不是充分条件，但在这里并不重要。）但是，由于我们刚刚观察到 a[i - s[j]] <= a[s[j]]，我们知道 a[i - s[m]] < a[s[j]]，这意味着 a[i - s[m]] 必须已经作为第一项出现在我们之前处理过的对和中！这与 m > j 相矛盾，这意味着没有这样更好的对和存在，因此我们可以安全地停止。

我期望第二个条件可以减少很多内部循环的次数；第一个条件可能只对数据集中有一些小数字和很多非常大的数字，并且可以用小数字的配对和来覆盖大部分位置的情况下有所帮助。

额外的效率：如果我们实现了上述第二个条件，那么我们实际上不需要单独的 j < i / 2 循环终止测试，因为在检查任何 i / 2 + 1 对之后，我们必须至少遇到一次重复的对和（第一项和第二项交换），这将导致条件2触发并退出循环。

伪代码：

s[1 .. k] = 1 .. k
sort s using comparator function comp(i, j) { a[i] < a[j] }

for i = k + 1 to n
  a[i] = max_value
  for (j = 1; a[s[j]] < a[i] && a[i - s[j]] > a[s[j]]; ++j)
    a[i] = min(a[i], a[s[j]] + a[i - s[j]])

- j_random_hacker

Answer 2

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

我同意评论中的观点，您很可能无法超越O(n^2)。因此，您最好的选择可能是尝试像这样的优化代码以减少n^2前面的系数。

- Rainbacon