这是我在stackoverflow上的第一个问题。我一直在解决Goodrich,Tamassia的“算法设计”中的一些练习题。然而,对于这个问题我感到很困惑。不确定从哪里开始,如何进行。任何建议都会很棒。以下是问题:
布尔矩阵是每个条目为0或1的矩阵,并且使用AND作为*和OR作为+执行矩阵乘法。假设我们有两个NxN随机布尔矩阵A和B,使得其中任何一个条目为1的概率为1/k。请证明,如果k是一个常数,则存在一种算法可以将A和B相乘,其期望运行时间为O(n^2)。如果k是n呢?
布尔矩阵是每个条目为0或1的矩阵,并且使用AND作为*和OR作为+执行矩阵乘法。假设我们有两个NxN随机布尔矩阵A和B,使得其中任何一个条目为1的概率为1/k。请证明,如果k是一个常数,则存在一种算法可以将A和B相乘,其期望运行时间为O(n^2)。如果k是n呢?