算法复杂度: Strassen's algorithm is polynomially faster than n-cubed regular matrix multiplication. "polynomially faster"是什么意思？

Question

Strassen 的算法在多项式上比 n 次方正则矩阵乘法快。 “多项式更快”是什么意思？

Answer 1

您的问题与“复杂性”的理论概念有关。例如，据说正则矩阵乘法的复杂度为 O(n^3)。这意味着随着维度“n”的增长，运行算法所需的时间 T(n) 保证不会超过函数“n^3”(三次函数)相对于正常数。正式地，这意味着:

存在一个正阈值 n_t，使得对于每个 n >= n_t，T(n) <= c * n^3，其中 c > 0 是某个常数。

在您的案例中，Strassen 算法已被证明具有复杂度 O(n^ log7)。由于 log7 = 2.8 < 3，因此随着 n 的增长，Strassen 算法保证比经典乘法算法运行得更快。

作为旁注，请记住，对于非常小的 n 值(即当 n < n_t 以上)，此声明可能不成立。