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

Question

3

大家都熟悉常数 O(1)或线性 O(N)的空间复杂度。

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

附言：我已经在各种网站上进行了调查，但没有得到任何令人满意的解决方案。

- Vaibhav Angi

你应该将这个移到讨论区。 - Muhammad Arshad

任何返回大小为f(N)的结果的算法，至少需要额外的O(f(N))空间（当然，前提是结果不与输入共享空间）。 - Mo B.

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 463035818_is_not_a_number · Accepted Answer

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

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