我可以证明2*2的矩阵A的平方是O(n^log5),它只需要5次乘法到目前为止,我没有问题,但是当我想解释为什么我们不能把它推广到其他平方的情况(不同的n*n大小)的2个原因之后,我可以提出如下一个:
我能想到的第一个原因是,我把3*3矩阵和它本身相乘,得出结论,它至少有6次相乘,所以它的运行时间至少是o(n^log6),这是n^epsalon大于o(n^log5),所以它比较慢,我们不能把o(n^log5)推广到所有情况。现在我需要另一个原因,但我不知道如何解释第二个原因,有人能帮忙吗(我只需要一个提示来想出一个主意)?

最佳答案

你不可能从例子中得到big-o符号的运行时间符号表示告诉我们算法的复杂性是如何随着参数的增加而增大的(在这个例子中是矩阵大小n),所以如果你真的想通过实验来近似它,你必须至少计算几个测试大小的运行时间。
但我怀疑你能找到手工制作100x100矩阵的最佳方法这实际上是个难题我们确定的是,它并不比矩阵乘积复杂。对于那些,我们有一个ω(n^2)的下界,因为我们必须至少看一次矩阵的每个条目。并且我们得到了近似(O)(n ^ 2.3729)的(理论)完美算法的上界,因为有一个复杂的已知算法。(见http://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication
顺便提一句,2.3729

关于algorithm - 平方矩阵和运行时间,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/21961527/

10-08 21:57
查看更多