求计算复杂度

在谈到算法的运行时间时，通常将最简单的函数 AsymptoticEqual (big ) 赋予精确运行时间函数。 陈述这种相等关系的另一种方式是每个函数都 AsymptoticLessEqual (big ) 和 AsymptoticGreaterEqual (big ) 另一个函数。下面以 Strassen 算法为例，对这些概念进行说明，该算法是发现的第一个 subcubic 矩阵乘法算法。

该算法包括四个步骤：将每个 矩阵分割为 4 个子矩阵，从 8 个子矩阵形成 14 个线性组合，将这 7 对组合相乘，并对 7 个结果求和。因此，计算乘法的时间 将是分割矩阵的恒定时间 ，在第二步和第四步形成线性组合所用的时间 ，以及第三步花费的时间 。

求递归关系式。

尽管结果有点儿复杂，但 。

同样地， 和 。

注意 ，所以算法是 subcubic 的。

比较原始立方算法和 Strassen 算法的增长率。