为什么定义为O（n^3）的矩阵乘法的时间复杂度？

Question

我在多个来源（在线和书籍）中遇到过这种情况 - 对于nXn大小的矩阵，方阵乘法的运行时间为O（n^3）。 （例如 - matrix multiplication algorithm time complexity）

该声明表明该乘法过程的运行时间的上限为C.n^3，其中C是某个常数，n> n0，其中n0是超出该上限的某个输入。 （http://en.wikipedia.org/wiki/Big_O_notation和What is the difference between Θ(n) and O(n)?） 问题是，我似乎无法推导出常数C和n0的值。

我的问题 -

1. 有人可以提供的声明数学证明 '方形矩阵乘法的大哦O（N^3）'？

2. C和n0的值是多少？

Answer 1

1. 有3内彼此会从0到n-1（或1至n）的每个（如可以看到的in the link you provided，即使它不完全正确的），这导致在环路O（n ）。将其正式化为适当的证明应该很容易。

2. a）对于形式证明，运行时间需要根据一些操作集来定义，通常被认为是任何算术操作。内的3 for循环有2个算术运算（1次乘法，1分相加），从而我们得到2.n3，从而C = 2

   B）N0 = 0，因为该保持从n = 1的

真

需要注意的是，由于big-O只是一个上界，我们也可以说这个算法的复杂度是O（对于任何k> = 3而言，都是0）（如果我们使用big- Theta符号）。我们还可以将C和n0分别设为大于2和0的任何值（因为要求不是要找到最小的可能值）。