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 回答