algorithm - 什么是可能的循环不变量

Question

有人可以为以下简单算法提供一个可能的循环不变式:

输入:A[0,...,n-1] 和 B[0,...,m-1]，每个都可能包含重复元素

输出:满足 A[i] == B[j] 的第一对 (i,j)。

算法:

for i <- 0 to n-1
    for j <- 0 to m-1
        if A[i] = B[j] then
           return (i,j)
        endif
    endfor
endfor
return null

到目前为止，我只有一个可能有效或可能无效的解决方案:

S = {(i,j) | A[0,...,i-1] 和 B[0,...,j-1] 没有公共(public)元素

Answer 1

在第一个循环的 pth 迭代内的第二个循环的 qth 迭代开始时，A[i] != B[j] 对于所有 i = 0...p - 1, j = 0...q - 1。