<分区>
我读了很多 papers关于矩阵向量乘法(BLAS2)和矩阵矩阵乘法(BLAS3)的性能优化。我想考虑这些优化是否/如何应用于 O(n^2) 和 O(n^3) 算法，这些算法不会干净地减少到密集或稀疏线性代数。
很容易找到 NP 完全或 NP 难算法的列表，但我还没有找到常见(和不太常见的)多项式时间算法的良好分类。谁能提出一个多项式时间问题的列表，其中最著名的算法是 O(n^2) 或 O(n^3)？
编辑:为了使这个更具体，我正在寻找类似 this list of NP-complete problems 的内容，但对于 多项式 问题，则改为使用 n^2 或 n^3 算法。
最佳答案
首先:值得注意的是，二级和三级BLAS操作的复杂度实际上形式上是O(n)和O(n^3/2)；输入矩阵本身是人们通常认为的“n”的二次方。
常用于密集线性代数的技术并不真正直接应用于其他问题领域，因为它们往往大量使用问题的线性度。
接下来:O(n^2) 算法的一些最常见示例是用于排序、整数乘法和计算离散傅里叶变换的朴素算法。在所有这些情况下，都存在复杂度较低的更好算法。同样，还有大量朴素的 O(n^3) 算法。
可以应用密集线性代数技术来计算 DFT(因为它也是线性的)，但您可以通过使用其中一种 FFT 算法做得更好，因此实际上没有人这样做。
就非朴素算法而言，自从我不得不教授复杂性类(class)以来已经太久了； IIRC，用于确定字符串是否使用上下文无关语言的最著名算法是 O(n^3)。
关于algorithm - 不是线性代数的 O(n^2) 和 O(n^3) 算法列表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12484831/