当A和B被排序时,找到最小A [i] ^ 2 + B [i] ^ 2

给定两个数组A和B长度n.A按升序B排序,按降序排序.查找i"产品" A[i]^2 + B[i]^2最小的索引.

我需要一个解决方案,O(log(n))其中包含所需的复杂性.

示例案例:

>>> A
[0, 4, 10, 12, 17, 28, 31, 32, 35, 39]
>>> B
[39, 34, 34, 31, 27, 23, 19, 11, 3, 2]

这里"乘积"被i = 4最小化

>>> [A[i]**2 + B[i]**2 for i in range(10)]
[1521, 1172, 1256, 1105, 1018, 1313, 1322, 1145, 1234, 1525]
>>> min(range(10), key=lambda i: A[i]**2 + B[i]**2)
4

Edgar Rokjān.. 11

在我看来,你的问题的答案是"否",线性算法是最快的.

建设性地,我们可以构建任何长度的序列,其在该序列内的任何随机位置具有最大值.此外,在这些序列上构建的平方和序列是无序的,因此您不能使用适合于排序序列的二分搜索等技术.

例如,如果我们有两个长度数组7:

5   8   10  11  12  14  15
12  11  10  9   7   6   1

我们得到如下数组的平方和:

169  185  200  202  193  232  225

我们可以看到,最大值是232,但除了迭代整个数组之外没有办法找到它,因为正方形和的序列是未排序的,最大值位于某处.

同样使用一个数组被排序的事实是无用的,因为第二个数组可能会对总和产生很大的影响,并且没有必要在单个数组上使用类似二进制搜索的东西来尝试评估总和.

我敢肯定,这个问题相当于找到未排序数组中最大的元素,其中线性解决方案最快.

在我看来,你的问题的答案是"否",线性算法是最快的.

建设性地,我们可以构建任何长度的序列,其在该序列内的任何随机位置具有最大值.此外,在这些序列上构建的平方和序列是无序的,因此您不能使用适合于排序序列的二分搜索等技术.

例如,如果我们有两个长度数组7:

5   8   10  11  12  14  15
12  11  10  9   7   6   1

我们得到如下数组的平方和:

169  185  200  202  193  232  225

我们可以看到,最大值是232,但除了迭代整个数组之外没有办法找到它,因为正方形和的序列是未排序的,最大值位于某处.

同样使用一个数组被排序的事实是无用的,因为第二个数组可能会对总和产生很大的影响,并且没有必要在单个数组上使用类似二进制搜索的东西来尝试评估总和.

我敢肯定,这个问题相当于找到未排序数组中最大的元素,其中线性解决方案最快.

这是一个简单的对抗性论点,即如果不考虑所有观点,就无法找到答案.也就是说,该算法为对手提供了一个可能自适应的索引序列来进行检查,并且对手将始终填写一个保留单调性约束的A和B,这将使算法无法在不查询的情况下得到正确的答案.地点.

对于某些给定的N,只考虑2d平面的右上象限.对手将只在单位四分之一圆上堆叠东西,在极坐标中等距离除了最后一个查询.最后,对手会将第N个项目简单地查询到圈内.因此,最后查询的索引是正确的答案.如果查询少于N个,并且算法选择一个查询位置,则攻击者坚持认为一个剩余的未查出位置几乎不在圆圈内,这意味着正确答案的距离小于1,但算法返回距离1.算法选择一个未经检验的位置,对手将它放在圈外.

正式埃德加的直觉为实际的细胞探测下限,考虑定义,用于i在[1, n]和一些j未知的算法,

X[i] = 2 * (n**2 + i)
Y[i] = 2 * (n**2 - i)
A[i] = X[i] + 1 if i == j
       X[i]     if i != j
B[i] = Y[i] + 1 if i == j
       Y[i]     if i != j

我们对A[i]**2 + B[i]**2假设做了一些分析i != j.

A[i]**2 + B[i]**2 == 4 * n**4 + 8 * n**2 * i + 4 * i**2
                       + 4 * n**4 - 8 * n**2 * i + 4 * i**2
                  == 8 * n**4 + 8 * i**2
                  <= 8 * n**4 + 8 * n**2

现在假设i == j.

A[i]**2 + B[i]**2 == 8 * n**4 + 8 * n**2 + 8 * i**2 + 2
                  >= 8 * n**4 + 8 * n**2 + 2

后者总是大于前者.(唉,我们想要一个最小值,而不是一个最大值.这个想法应该基本相同 - 只减少一个而不是增加一个 - 但是代数略有不同.)

j除了at之外,具有变化的阵列对的族看起来相同j,因此算法必须平均检查一半的索引以确定j,这对于该族发现正确的输出是同义的.