algorithm - O(1), O(n), O(n*n) 内存是什么意思？

Question

这个问题在这里已经有了答案:

关闭 10年前.

Possible Duplicate:
Plain English explanation of Big O

很多时候，当谈到算法的时间复杂度时，内存也会被考虑在内。我想知道big-O(1)、big-O(n)、big-O(n*n)内存是什么意思？

它与时间复杂度有什么关系？

Answer 1

正如 xmoex 所说:

o(1) 构成恒定的内存使用量。所以输入量是无关紧要的。

o(n) 构成线性内存使用。所以更多的输入意味着线性更多的内存。

o(n*n) 构成二次内存使用。所以更多的输入意味着更多的内存(平均 x^2。

在大多数情况下，这种内存复杂度度量完全独立于时间复杂度的度量。对于计算机算法，重要的是要知道算法将如何管理这两种复杂性以决定算法的质量。但是，两者必须分别计算。一个可能比另一个更重要，具体取决于您的用例和问题环境。