以这样的方式填充数组，即每个元素等于两个数字的最小总和

Given an array (contains only positive integers) that already has the first k elements: a₁, a₂, .... a_k.
I need to fill the remaining (n - k) elements (the array has n elements in total).
The value of n is about 10 ^ 3 and 1 <= k <= n.
The value of each a_i is the minimum sum of two numbers such that the sum of positions of those two numbers is equal to i.

Here is the pseudocode (my algorithm):

给定一个已经有前k个元素的数组(只包含正整数):a1,a2,.... ak。我需要填充剩余的(n-k)元素(数组总共有n个元素)。 n的值约为10 ^ 3且1 <= k <= n。每个ai的值是两个数的最小和,使得这两个数的位置之和等于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])

Time complexity: O(n ^ 2)

The question: Is there any other way to do this faster?
I'm looking for any data structures or algorithms that can find the value of each a_i in less than O(n).

P/S: This is a procedure in my program so I need to do this as fast as possible.

时间复杂度:O(n ^ 2)问题:还有其他方法可以更快地完成这项工作吗?我正在寻找能够找到每个ai的值小于O(n)的任何数据结构或算法。 P / S:这是我程序中的一个程序,所以我需要尽快完成。

2 个解决方案

#1

You could increase your program speed by using threads to run your check for the minimum value in parallel. For example you could run 4 threads each of which checks 1/4 of the range of j. This will improve the speed marginally, but your algorithm will still take O(n^2) running time.

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

I agree with the comment that you most likely can't get beyond O(n^2). So your best bet will probably be to try things like this to optimize your code to reduce the coefficient in front of that n^2.

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

#2

Idea 1

AFAICT this will not give a guaranteed improvement on O(n^2), but it should bring the number of inner loop cycles down a lot in practice. The basic idea is that we can test pairs in the inner loop in a different order that enables us to finish early a lot of the time. Specifically we first make a sorted list of positions of the numbers and store this in s[], so that a[s[i]] is the ith smallest number in a[]. Then in the main inner loop, we form pair-sums in increasing order of the first term by using a[s[j]] instead of a[j] (and a[i - s[j]] instead of a[i - j]). This gives us 2 ways to stop the inner loop early:

AFAICT这不会对O(n ^ 2)提供有保证的改进,但它应该在实践中使内循环周期的数量减少很多。基本思想是我们可以以不同的顺序在内循环中测试对,这使我们能够在很多时候提前完成。具体来说,我们首先制作一个排序的数字位置列表并将其存储在s []中,这样a [s [i]]就是[]中第i个最小的数字。然后在主内循环中,我们通过使用[s [j]]而不是[j](和[i - s [j]]而不是[i]来以第一项的递增顺序形成对和 - j])。这为我们提供了两种早期停止内循环的方法:

1. If a[s[j]] >= a[i], then we can stop because every later sum must be larger, since the first term of each of them (a[s[j+1]] etc.) must be at least as large as the best solution so far (already in a[i]), and the other term can never be negative.

如果[s [j]]> = a [i],那么我们可以停止,因为每个后来的总和必须更大,因为它们中的每一个的第一项(a [s [j + 1]]等)必须是至少与迄今为止最好的解决方案一样大(已经在[i]中),而另一个术语永远不会是负面的。

2. If a[i - s[j]] <= a[s[j]] (that is, if the "partner" of the next smallest number is less than or equal to it), we can stop, for a more complicated reason. Suppose to the contrary that there was some better pair-sum a[s[m]] + a[i - s[m]] later on (i.e. m > j). We know the first term, a[s[m]], must be at least as large as our current first term a[s[j]] because we're accessing first terms in increasing order, and m > j; therefore, for the pair-sum a[s[m]] + a[i - s[m]] to be better (i.e. less) than a[s[j]] + a[i - s[j]], it must be that its second term, a[i - s[m]], is less than our current second term, a[i - s[j]]. (This is not a sufficient condition, but that doesn't matter here.) But since we have just observed that a[i - s[j]] <= a[s[j]], we know that a[i - s[m]] < a[s[j]] too, which means that a[i - s[m]] must have appeared as a first term in a pair-sum that we already processed earlier on! That contradicts m > j, meaning that no such better pair-sum can exist, so we can safely stop.

如果[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]]比[s [j]] + a [i - s [j]]更好(即更少),必须是它的第二个词,[i - s [m]],小于我们当前的第二个词,a [i - s [j]]。 (这不是一个充分的条件,但这并不重要。)但是因为我们刚刚观察到[i - s [j]] <= a [s [j]],我们知道[i - s [m]] j相矛盾,这意味着没有更好的配对可以存在,所以我们可以安全地停止。

I expect the second condition to remove a lot of inner loop cycles; the first will probably only help much on datasets where there are a few small numbers and a lot of very high numbers, and it is possible to cover most positions with pair-sums of the small numbers.

我希望第二个条件可以消除很多内循环周期;第一个可能只对数据集有很大帮助,这些数据集中有一些小数字和很多非常高的数字,并且可以用小数的对和来覆盖大多数位置。

Bonus efficiency: If we implement the second condition above then we don't actually need a separate j < i / 2 loop termination test, since after examining any i / 2 + 1 pair-sums, we must have encountered at least one pair-sum twice (once with the first and second terms swapped), and this will cause condition 2 to fire and exit the loop.

额外效率:如果我们实现上述第二个条件,那么我们实际上并不需要单独的j

Pseudocode:

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]])