布尔矩阵乘法算法

Question

这是我在stackoverflow上的第一个问题。我一直在解决Goodrich，Tamassia的“算法设计”中的一些练习题。然而，对于这个问题我感到很困惑。不确定从哪里开始，如何进行。任何建议都会很棒。以下是问题：

布尔矩阵是每个条目为0或1的矩阵，并且使用AND作为*和OR作为+执行矩阵乘法。假设我们有两个NxN随机布尔矩阵A和B，使得其中任何一个条目为1的概率为1/k。请证明，如果k是一个常数，则存在一种算法可以将A和B相乘，其期望运行时间为O(n^2)。如果k是n呢？

- user4452139

Answer 1

使用标准迭代方法进行矩阵乘法的时间复杂度为O(n³)，因为您需要遍历n行和n列，并且对于每个元素，需要对一行和一列进行向量乘法，这需要n个乘法和n-1个加法。

矩阵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”为真，就可以停止计算并提前退出最内层循环，因为将任何后续值与true进行OR运算都会产生true，所以我们可以立即知道最终结果将为true。

对于任意常数k，在我们能够提前退出之前（假设值是随机的），操作次数将取决于k，并且不会随n的增加而增加。在每次迭代中，循环终止的概率是(1/k)²，因为我们需要两个1才能发生这种情况，并且每个条目是1的概率是1/k。在终止之前的迭代次数遵循几何分布，其中p是(1/k)²，在“成功”（退出循环）之前的预期“试验”（迭代）次数不取决于n（除了作为试验次数上限），因此对于给定的k，内部循环平均运行时间为常数时间，从而使整体算法的时间复杂度为O(n²)。几何分布公式应该可以让您了解如果k = n会发生什么。请注意，在Wikipedia上给出的公式中，k是试验次数。

- samgak

---

当k很大时，你几乎永远不会提前退出，你的算法将是O(n^3)。 - Paul Hankin

@匿名大O符号定义了函数的极限行为。无论k有多大，当n趋近于无穷大时，执行时间将趋向于O(n^2)，对于给定的k。 - samgak

没错，这个问题很令人困惑，因为它既提到了k是常数，又提到了k=n。请问需要如何解决？ - Paul Hankin

我想将我的踩转为赞，但是除非您编辑您的回答，否则我的投票是锁定的。您能进行一次微不足道的编辑吗？ - Paul Hankin

@Anonymous- samgak 在这里是正确的。您现在可以点赞此答案。 - Am_I_Helpful

非常感谢您的全面回答！ :) - user4452139