使用标准迭代方法的矩阵乘法是 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 是试验次数。