我可以比线性时间更快地搜索两个数组中的条目“a[i] + b[i] > N”吗？

Question

我有两组数组，

a

和

b

，长度均为

n

。如果我选择一个

a

和一个

b

，我知道

a[i] <= N

和

b[i] <= N

代表所有

0 <= i < n

。计算所有

a[i] + b[i] <= N

是否为

i

的最有效方法是什么？

目前，我只是循环遍历数组并比较

a[0] + b[0] <= N

、

a[1] + b[1] <= N

等。显然，这是一种

O(n)

方法。

有什么方法可以预处理

a

s 和

b

s 数组，以便搜索总和

a[i] + b[i] > N

可以比线性时间更快完成？

Answer 1

如果您无法进行预处理，那么

O(n)

是您能拥有的最好的。通过矛盾证明：假设给你一些比

O(n)

更好的算法；这意味着对于一些大的

n

，某些索引将被跳过（因为该算法具有比线性时间复杂度更好的性能）。我们可以构造一个反例；让我们运行足够大的算法

n

a[i] = 0,     for all i
b[i] = N - 1, for all i

如果算法返回

false

（即对于某些

j

a[j] + b[j] > N

），它是不正确的。如果算法返回

true

它会跳过 一些索引，例如索引

k

（因为该算法比线性算法更好并且

n

足够大）。所以反例就是

a[i] = 0,     for all i, except k
b[i] = N - 1, for all i

a[k] = 2

算法将返回

false

（当所有其余值与第一次运行中的值相同时，将跳过索引

k

），现在这是不正确的。

如果你可以预处理

a

和

b

数组，你可以计算

max = Max(a[i] + b[i])

然后返回

max <= N

具有

O(1)

时间和空间复杂度

Answer 2

另一个答案假设未排序的数组，但是，我认为最好提及数组已排序的情况。

如果两个数组都已排序，那么计算是 O(1)，因为我们只需要检查最后一个元素的总和是否满足规则：

a[n-1] + b[n-1] <= N

如果满足这一点，则该规则适用于所有指数。