布尔矩阵乘法算法

Question

这是我关于stackoverflow的第一个问题.我一直在解决Tamassia的Goodrich的"算法设计"中的一些练习.但是,我对这个问题很无能为力.Unusre从哪里开始以及如何继续.任何建议都会很棒.这是问题所在:

布尔矩阵是矩阵,使得每个条目为0或1,并且通过使用AND for*和OR for +来执行矩阵乘法.假设我们给出了两个NxN随机布尔矩阵A和B,因此任一条中的任何条目为1的概率为1/k.证明如果k是常数,那么有一个算法用于乘以A和B,其预期运行时间为O(n ^ 2).如果k是n怎么办？

Answer 1

使用标准迭代方法的矩阵乘法是O(n ³),因为你必须遍历n行和n列,并且对于每个元素,执行一个行和一个列的向量乘法,其乘以n乘法和n-1个补充.

Psuedo代码将矩阵a乘以矩阵b并存储在矩阵c中:

for(i = 0; i < n; i++)
{
    for(j = 0; j < n; j++)
    {
        int sum = 0;
        for(m = 0; m < n; m++)
        {
            sum += a[i][m] * b[m][j];
        }
        c[i][j] = sum;
    }
}

对于布尔矩阵,如问题中所指定的,使用AND代替乘法和OR代替加法,因此它变为:

for(i = 0; i < n; i++)
{
    for(j = 0; j < n; j++)
    {
        boolean value = false;
        for(m = 0; m < n; m++)
        {
            value ||= a[i][m] && b[m][j];
            if(value)
                break; // early out
        }
        c[i][j] = value;
    }
}

这里要注意的是,一旦我们的布尔"sum"为真,我们就可以停止计算并提前退出最内层循环,因为将任何后续值与OR进行或运算将产生真,所以我们可以立即知道最终结果将是真的.

对于任何常数k,我们可以提前做出的操作数(假设值是随机的)将取决于k并且不会随n增加.在每次迭代时,循环将有一个(1/k)^2的机会终止,因为我们需要两个1才能发生这种情况,每个条目为1的几率为1/k.终止前的迭代次数将遵循几何分布,其中p为(1/k)²,并且"成功"(突破循环)之前的预期"试验"次数(迭代次数)不依赖于n(除了作为试验次数的上限之外,所以对于给定的k,最里面的循环以恒定时间(平均)运行,使得整个算法O(n ²).如果k = n,几何分布公式应该可以让您了解会发生什么.请注意,在维基百科上给出的公式中,k是试验次数.