big-o - 为什么方阵乘法的时间复杂度定义为 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 的值。

我的问题——

有人可以为“方阵乘法的大哦是 O(n^3)”这一陈述提供数学证明吗？

C 和 n0 的值是多少？

Answer 1

彼此内部有 3 个 for 循环，每个循环从 0 到 n-1(或 1 到 n)(可以看出 in the link you provided ，即使它不完全正确)，这导致 O(n3)。将其形式化为适当的证明应该很容易。

a) 对于形式证明，运行时间需要根据一些运算集来定义，通常被视为任何算术运算。在 3 个 for 循环中，有 2 个算术运算(1 个乘法，1 个加法)，因此我们得到 2.n3 ，因此 C = 2。
b) n0 = 0 因为这适用于 n = 1

请注意，由于 big-O 只是一个上限，因此我们也可以说该算法的复杂度对于任何 k >= 3 都是 O(nk)(如果我们使用 big-Theta 表示法，则情况并非如此)。我们还可以将 C 和 n0 分别取为大于 2 和 0 的任何值(因为要求不是找到可能的最小值)。