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

Question

因此，每个人都熟悉常量 O(1) 或线性 O(N) 空间复杂度。

但我有一个问题，是否存在算法的空间复杂度与 O(NLogn) 或 O(N^2) 成正比的情况。如果可能的话，它的优势是什么。

P.S.- 我研究过各种网站，但没有找到任何令人满意的解决方案。

Answer 1

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

一般来说，使用矩阵的算法通常采用 N*N存储矩阵的内存。例如旋转 N=3 中的一个点尺寸，您可以使用 3x3旋转矩阵。