algorithm - 算法复杂性：Strassen 的算法在多项式上比 n 立方正则矩阵乘法要快。“多项式更快”是什么意思？

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 以上时），此语句可能不成立。

Answer 2

具有复杂性O(n^3)且O(n^2)两者都是多项式的算法。但第二个是多项式更快。

Answer 3

在这种情况下，我假设这意味着两种算法都有多项式运行时间，但 Strassen 算法更快。

那只是因为标准（即使是立方体）是多项式的。

无论如何，我不认为“多项式更快”这个术语是一个标准术语。