6

这是我关于stackoverflow的第一个问题。我一直在解决一些来自塔马西亚古德里奇的“算法设计”的练习。但是，我对这个问题一无所知。Unusere 从哪里开始以及如何进行。任何建议都会很棒。这是问题所在：

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

4

1 回答 1

9

使用标准迭代方法的矩阵乘法是 O(n 3 )，因为您必须迭代 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，所以我们可以立即知道最终结果将是真的。

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

于 2015-04-13T13:23:03.800 回答