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

Question

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

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

输出：第一对 (i,j) 使得A[i] == B[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] and B[0,...,j-1] has no common elements}

Answer 1

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