算法A时间复杂度O(n²)，算法B时间复杂度为O(n³)，为什么选择算法B而不选算法A的6个理由? 第1页

• 空间复杂度过大，空间换时间但目标机器空间不足。
• 数据量过小，效率更高的算法耗用时间相对更长。如常数时间每次查询都需要1毫秒，而平方复杂度在数据量低于某个值时只需几十个纳秒，那么显然后者为好。一个典型案例就是对quick sort算法的优化：当数据分割到小于等于6个元素时改用复杂度高半级的冒泡排序，最终表现却比纯粹的quick sort更好。另一个案例是哈希表，当数据量较小时二分法查找只需十几次访问，哈希表本身的哈希算法却可能需要执行很多条指令（当然现在因为内存速率和CPU严重不匹配，cache miss本身消耗的额外时间可能就足够执行哈希算法了，具体哪个更好用需要先做测试才能确定）。
• 时间消耗不稳定，如常数时间的哈希表在冲突发生时退化到链表，而对数复杂度的二分法稳定在对数复杂度。那么对于实时系统，哈希表可能就是不可行的。
• 数据准备/维护代价过大。比如一个对数查询效率的数据结构，插入新数据的消耗可能是指数复杂度。
• 精度不足。如布隆过滤器效率O（1），但只能确认数据不在集合中。而它报告数据存在时，数据却可能不在，也就是存在误判。类似的，有很多效率极高的近似算法，在需要精确解时显然是不能用的。
• 无法满足可靠性要求。比如如果某高效算法无法做到事务级可靠性（ACID）、或者在多线程场合表现极差，那么在可靠性不可忽略的场合自然不能使用。
• 对数据性质有苛刻要求。比如基数排序效率可达O（N），但要求数据必须是有限位的数字、每位符号数目有限且每个数字位满足进位值类似的权值约束。

好像一不小心说了七条，但似乎并没能涵盖所有情况...

问题：输入两个 的矩阵 ，计算矩阵乘积

实际用的算法：

直接法，一个一个老老实实乘。利用硬件的乘加融合、SIMD、Tensor Core，有明显的优化效果。

Strassen算法：

三个维度都对半切 ， ，

如果是直接法，就用左边的8个小矩阵块，可以通过4次小矩阵块的加法和8次小矩阵块的乘法，算出右边4个小矩阵块

而Strassen算法把计算公式变形，变成18次矩阵加法（ ）和7次矩阵乘法（递归的 ），具体看这篇文章

Strassen算法的两个问题：

1. 复杂度低阶项大。也就是小矩阵块加法从4次变成18次，虽然平方是低阶项，但是在实际的有限规模下不能忽略。而且，矩阵加法的主要开销不是每个元素的浮点加法，而是内存访问（或者说cache的启动缺失）。
2. 浮点精度低。 和 不是2个乘积之和，而是4个乘积之和，把4个乘积的误差累积起来了；递归算下去，对角线附近的元素要经过 次乘加的误差累积。

目前已知的渐进复杂度的极限：

把上面的数字一般化，每个方向分成 份，变成 次矩阵乘法，复杂度变成

考虑更大的 。比如 时， 不一定是 。因为两层合到一起以后有更多的公式变形机会，乘法次数有可能更少，渐进复杂度更低；但是公式变形的代价是加法更多，低阶项更大，有可能精度更低。

目前已知的渐进复杂度的极限是令 ，取 得到的极限。