我在多个来源（在线和书籍）中遇到过这个问题 - 对于大小为 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 的任何值（因为要求不是找到可能的最小值）。