O(1), O(n), O(n*n)内存的含义是什么？

Question

可能是重复的问题:
Big O的简单解释

当我们谈论算法的时间复杂度时，有时也会考虑到内存。我想知道big-O(1)、big-O(n)、big-O(n*n)内存的含义是什么？

以及它们与时间复杂度的关系如何？

- Eight

---

重复：https://dev59.com/WlDTa4cB1Zd3GeqPKI5R - Stealth Rabbi

衡量复杂度，而非内存。 - Stealth Rabbi

我猜你在谈论“大O符号”（或“大O”）。这在以下维基百科页面中有详细解释：http://en.wikipedia.org/wiki/Big_O_notation - Yuri

你是指 o(n) 还是 O(n)？它们之间有很大的差异。 - Fred Foo

@NullUserExceptionఠ_ఠ：嗯，OP明确要求空间和时间复杂度之间的关系，但那里没有涉及到。虽然我觉得这个问题比较宽泛，但我不会投票关闭它作为重复问题。 - Fred Foo

Answer 1

正如xmoex所说：

o(1)表示常数级别的内存使用，因此输入量大小并不重要。

o(n)表示线性内存使用，因此输入量增加会导致内存线性增加。

o(n*n)表示二次内存使用，因此输入量增加会导致内存呈平方级别增加（平均为x^2）。

大多数情况下，这种内存复杂度与时间复杂度是完全独立的。对于计算机算法来说，了解算法如何管理这两个复杂度是很重要的，以决定算法的质量。但是，这两个复杂度必须分别计算。根据问题的使用情况和环境，其中一个可能比另一个更重要。

- mikecline

---

当算法所使用的空间为o(f(n))（即小o）时，它所花费的时间也是o(f(n))。 - Fred Foo

这并非总是如此。是的，内存和时间的复杂度可能相同。然而，也有可能存在一种算法，其所需时间少于所需空间。空间复杂度可以为o(f(n))，而时间复杂度可以大于o(f(n))。 - mikecline

再说一遍，那是不正确的。Lowerbound 是 omega 而不是小写的 omicron。小-o 意味着它保证比某个值更低，而不是低于或等于该值。大-O 表示 <=，小-o 表示 <，大-Omega 表示 >=，小-Omega 表示 >，theta 表示既 <= 又 >=，~ 表示在所有广泛的目的下等于。 - mikecline

你说得对，我的符号表示错了。然而，“完全独立”仍然不是真的。你不能在图灵机上用比空间更少的时间完成任务。 - Fred Foo

但是可以使用图灵机将事物分解成“线程”，因此，由于事物在并行运行，因此某些事物可能需要的时间比表示问题所需的空间少。 - mikecline

Answer 2

o(1)表示平均内存使用是固定的，不管您的输入大小如何
o(n)表示如果您正在处理n个元素，则您的平均内存需求会线性增长
o(n*n)表示如果您正在处理n个元素，则您的平均内存需求将呈二次增长

有一篇维基百科文章介绍了所谓的大O符号（也涵盖了小o…）

- xmoex

Answer 3

在记忆方面，复杂性意味着当要处理的项目数量增加时，所需内存大小的增长速度。一个很好的例子是排序算法。

• O(1)和O(log n)表示，在对N个项目进行排序时，算法需要的内存少于为N个项目分配的总内存。(即原地排序)
• O(n)-内存消耗是线性的，因此随着项目计数的增长而增长内存消耗
• O(n*n)表示算法需要更多的额外内存。

- sll

---

"O(n * n)意味着算法需要更多的额外内存，这是非常模糊的。最好指定它需要二次数量的内存。尽管如此，对于简单易懂的解释还是要点赞。" - adelriosantiago

Answer 4

这里有人解释了大O符号的含义。因此，我不会再重复解释。但是，我会简要地解释一下。

拿一个没有循环的小程序来举例。

{ int a=1;
print("%d",a);
}

这个程序的执行时间可以忽略不计。假设声明和打印都只需要一定的时间，那么它的时间复杂度将是O(1)。

另一个程序有一个循环，运行n次。

{int a,i;
long n=10000000;
for(i=0;i<n;i++)
    // doing some calculations
}

如您在这里看到的，声明将需要可以忽略不计的时间，即O(1)。如果我们让第4行需要一些时间单位，即O(n)，那么总体时间复杂度将是

O(1)+O(n)=O(n).

现在您可以理解 O(n*n)，即 2 层循环。

为了更好地理解...

在未排序的列表中查找项目 = O(n)

通过简单算法或冒泡排序来乘以两个 n 位数 = O(n*n)

使用二进制搜索在已排序的数组中查找项目 = O(log n)

使用暴力方法解决推销员问题 = O(n!)

- Ravi Kumar

Answer 5

我不确定你是指大O还是小o，但我的回答会更普遍。

对于内存和时间来说，它的意思是相同的。如果一个函数在内存中增长为O（1），那么它使用恒定数量的内存，而不管输入大小。如果一个函数以O（n）增长，则使用线性数量，如果是O(n*n)，则使用二次方数量。

- Nick Garvey