我一直在阅读很多关于矩阵向量乘法 (BLAS2) 和矩阵矩阵乘法 (BLAS3) 的性能优化的论文。我想考虑这些优化是否/如何应用于 O(n^2) 和 O(n^3) 算法，这些算法不能完全简化为密集或稀疏线性代数。
很容易找到 NP-complete 或 NP-hard 算法的列表，但我还没有找到常见（和不太常见）多项式时间算法的良好细分。谁能建议一个多项式时间问题的列表，其中最著名的算法是 O(n^2) 或 O(n^3)？
编辑：为了使这一点更具体，我正在寻找类似这个NP-complete questions列表的东西，但是对于n^2 或 n^3 算法的多项式问题。
第一：值得注意的是，二级和三级BLAS操作的复杂度实际上形式上是O(n)和O(n^3/2)；输入矩阵本身就是人们通常认为的“n”的二次方。
通常用于密集线性代数的技术并不真正直接应用于其他问题域，因为它们倾向于大量使用问题的线性。
接下来：O(n^2) 算法的一些最常见示例是用于排序、整数乘法和计算离散傅里叶变换的朴素算法。在所有这些情况下，都存在具有较低复杂度的更好算法。同样，还有大量朴素的 O(n^3) 算法。
可以应用密集线性代数技术来计算 DFT（因为它也是线性的），但是使用 FFT 算法之一可以做得更好，所以实际上没有人这样做。
就非朴素算法而言，我不得不教授复杂性课程已经太久了。IIRC，用于确定字符串是否为上下文无关语言的最著名算法是 O(n^3)。