O(1),O(n),O(n*n)记忆的含义是什么？

Question

可能重复:
Big O的简单英文解释

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

它与时间复杂性有何关系？

Answer 1

正如xmoex所说:

o(1)构成恒定的内存使用.因此,输入量无关紧要.

o(n)构成线性内存使用.因此,更多输入意味着线性更多的内存.

o(n*n)构成二次​​存储器使用.因此,更多的输入意味着更多的内存(平均x ^ 2).

在大多数情况下,这种存储器复杂度的度量完全独立于时间复杂度的度量.对于计算机算法,重要的是要知道算法将如何管理这两种复杂性以决定算法的质量.但是两者都必须单独计算.根据您的使用案例和问题的情况,一个可能比另一个更重要.

Answer 2

o(1)表示恒定的平均内存使用,无论输入的大小如何
o(n)表示如果你正在处理n个元素,你的平均内存需求会增长线性
o(n*n)意味着如果你有n个元素你是处理时,你的平均内存需求会增长二次

有一篇关于所谓的大写符号的wiki文章(也涵盖了小o ...)