algorithm - O(n^2) 的空间复杂度

Question

因此，Everbody 都熟悉常数O(1)或线性O(N)空间复杂度。

但我有一个问题，算法的空间复杂度是否与O(NLogn)或成正比O(N^2)。如果可以，那有什么好处。

PS-我已经研究了各个站点，但没有得到任何令人满意的解决方案。

标签： algorithmcomplexity-theoryspace-complexity

Answer 1

几乎任何算法都可以使用O(N^2)内存。考虑一些计算成本高的f(a,b)地方。为了减少运行时间，一个明显的解决方案是使用带有预先计算结果的大小查找表。可以经常在运行时和内存使用之间进行这种权衡。0 < a,b < NfN * N

通常，使用矩阵的算法通常会占用N*N内存来存储矩阵。例如，要在N=3维度上旋转一个点，您可以使用3x3旋转矩阵。