Que*_*ger 5 big-o matrix-multiplication
我在多个来源(在线和书籍)中遇到过这种情况 - 对于大小为nXn的矩阵,方阵乘法的运行时间为O(n ^ 3).(例子 - 矩阵乘法算法时间复杂度)
该陈述将指示该乘法过程的运行时间的上限是Cn ^ 3,其中C是一些常数并且n> n0其中n0是一些输入,超过该输入,该上限保持为真.(http://en.wikipedia.org/wiki/Big_O_notation和Θ(n)和O(n)之间有什么区别？)问题是,我似乎无法推导出常数C和n0的值.
我的问题 -
有人可以提供一个数学证明的声明'方阵矩阵乘法的大哦是O(n ^ 3)'？
C和n0的值是多少？
每个循环中有3个for循环,每个循环从0到n-1(或1到n)(如您提供的链接中所示,即使它不完全正确),这会导致O(n 3).将其形式化为适当的证据应该很容易.
a)对于形式证明,运行时间需要根据一组操作来定义,通常被认为是任何算术运算.在3 for循环中有2个算术运算(1次乘法,1次加法),因此我们得到,因此C = 2.2.n3
b)n0 = 0,因为这与n = 1成立
注意,由于big-O只是一个上界,我们也可以说这个算法的复杂度对于任何k> = 3 都是O(n k)(如果我们使用big-Theta表示法则不一样).我们也可以将C和n0分别设置为大于2和0的任何值(因为要求不是找到最小的可能值).