令m，n为整数，使得0 <= m，n <N。
限定：
Algorithm A: Computes m + n in time O(A(N))
Algorithm B: Computes m*n in time O(B(N))
Algorithm C: Computes m mod n in time O(C(N))
使用算法A，B和C的任何组合描述了用于N×N矩阵加法和矩阵乘法的算法，其具有Z / NZ中的条目。同时指出算法的运行时间大O表示法。
尝试解决方案：
对于在Z / NZ中添加NXN：令A和B为Z / NZ中的NXN矩阵，其中条目a_ {ij}和b_ {ij}使得i，j在{0,1，...，N}中，其中i表示行，j表示矩阵中的列。另外，让A + B = C.
Step 1. Run Algorithm A to get a_{ij} + b_{ij} = c_{ij} in time O(A(N))
Step 2. Run Algorithm C to get c_{ij} mod N in time O(C(N))
对{0,1，...，N}中的所有i，j重复步骤1和2。
这意味着我们必须重复1,2 N ^ 2次的步骤。因此，总运行时间估计为
N^2[ O(A(N)) + O(C(N)) ] = O(N^2 A(N)) + O(N^2 C(N)) = O(|N^2 A(N)| + |(N^2 C(N)|).
对于乘法算法，我刚刚用算法B替换了步骤1，并像上面一样得到了总运行时间beO(|N^2 B(N)| + |(N^2 C(N)|)。
如果我正确地接近这个问题，请告诉我，特别是使用big-O表示法。
谢谢。
你的matrix multiplication算法是错误的，并且会产生错误的答案，因为A*B_{i,j} != A_{i,j} * B_{i,j}（除了像零矩阵这样的特殊情况）
我假设问题的目标不是实现有效的矩阵乘法，因为它是一个很难且仍在研究的问题，所以我将回答矩阵乘法的天真实现。
对于任何指数i，j：
(AB)_{i,j} = Sum( A_{i,k} * B_{k,j}) =
= A_{i,1} * B_{1,j} + A_{i,2} * B_{2,j} + ... + A_{i,k} * B_{k,j} + ... + A_{i,n} * B_{n,j}
正如你所看到的，每对i,j都有n乘法和qazxswpoi加法ץ关于n-1的调用数量 - 这取决于你是否需要在每次添加后调用它，或者只在你完成时调用一次（这实际上取决于有多少）你必须代表每个数字的位，所以对于每对C - 你可能需要它从一次到i,j invokations。
这给出了我们的总复杂度（假设每个（i，j）对有2n-1 modolus，如果需要更少，如上所述 - 相应调整）：
2n-1作为旁注，一个良好的健全性检查显示你的算法确实是错误的 - 证明矩阵乘法不能比O(n^3*A + n^3*B + n^3*C)
（Omega(n^2 logn)）做得更好，最好的当前实现是Raz,2002
~O(n^2.3)