小编Jer*_*Gao的帖子

当我查找矩阵乘法算法的维基百科页面时，问题就出现了

它说：

\n

该算法有一个关键路径长度的\xce\x98((log n)^2)步骤，这意味着在具有无限数量处理器的理想机器上需要那么多时间；因此，它在任何真实计算机上都有最大可能的加速\xce\x98(n3/((log n)^2))。

\n

（引用来自“并行和分布式算法/共享内存并行性”部分。）

由于假设有无限个处理器，乘法运算应该在 中完成O(1)。然后将所有元素相加，这也应该是一个常数时间。因此，最长的关键路径应该是O(1) 而不是 \xce\x98((log n)^2)。

我想知道 O 和 \xce\x98 之间是否有区别，我错在哪里？

问题已经解决，非常感谢@Chris Beck。答案应该分为两部分。

首先，一个低级错误是我没有计算求和的时间。求和进行运算O(log(N))（_{考虑二进制加法）}。

其次，正如克里斯指出的那样，重要的问题需要O(log(N))处理器花费时间。最重要的是，最长的关键路径应该是O(log(N)^2)而不是O(1)。

对于 O 和 \xce\x98 的混淆，我在Big_O_Notation_Wikipedia中找到了答案。

\n

Big O 是比较函数时最常用的渐近表示法，尽管在许多情况下 Big O 可以替换为 Big Theta \xce\x98 以获得渐近更紧的界限。

\n

我最后的结论是错误的。这O(log(N)^2)不会发生在求和和处理器处，而是发生在我们分割矩阵时。感谢@displayName 提醒我这一点。此外，Chris对非平凡问题的回答对于研究并行系统仍然非常有用。感谢下面所有暖心回答者！