n 位矩阵的算法

Question

给出了两个函数P1, P2，它们接受输入n位x，并计算y1=A1*x, y2=A2*x。 A1 和A2 是n*n 位矩阵。这两个函数返回 n 位数组 y1,y2。我们不知道关于这些矩阵的任何信息，但知道 A1 和 A2 除了一个插槽 (i,j) 之外是相同的。 (i 和 j 对我们来说是未知的)。我们可以为不同的x值调用P1和P2，然后比较这两个函数的输出。我想知道通过多少次调用我们可以找到 i, j？

在简短的回答中，我们的书写道:Log n calls。任何提示或想法？感谢大家。

编辑:有人说，首先 x 是一个“1”的列矩阵。并计算 y1 和 y2 并找到不同的行。那么 x 是一个矩阵，其中 n/2 向上元素为“1”，n/2 底部元素为“0”。如果 y1 和 y2 相等，区别在于 n/2+1 到 n 否则为 1 到 n/2...

Answer 1

如果可以转置 A1 和 A2，则可以在两次调用中完成:

您可以通过一次调用来确定 i，主要检查 y1 和 y2 中的哪个条目不同。这会给你 i。

转置A1和A2，做同样的事情，不同的条目是j的索引。

没有转置:你仍然做一次乘法来确定i。现在，只需执行“二进制搜索”，您的搜索区域将由 x 向量条目中的 1 标识。

第一步:用1填充x向量的一半，用0填充另一半，做乘法，检查索引处的条目是否i 是不同的，如果不是，那么你的 j 在第二部分的某个地方，如果不同，那么它是在你的前半部分(你感觉 1)

第二步:将上一步选择的部分一分为二，一半是1，另一半是0，重复相同的逻辑直到剩下只有一个条目。那个是你的 j

的索引

由于您总是一分为二，因此您将恰好有 log(n) 个调用。

Determine `i` entry by doing one call. (trivial)
length = n/2
start = 0
while(not found)
    var x[start..start+length) = 1 (0 all otter entries)
    do function calls
    if result1[i] == result2[i]
        start = 0
        length = length/2
    else
        start = length+1
        length = length/2
    if length == 1
        found.
        start is your index j