O(1)的空间复杂度是什么？

Question

O(1)的空间复杂度是什么？

66

我很难理解 O(1) 的空间复杂度是什么意思。我知道它表示算法所需的空间不随输入或使用算法的数据大小而增长。但这究竟意味着什么呢？

如果我们在一个链表上使用算法，比如 1->2->3->4，为了遍历到 "3"，我们会声明一个临时指针，并遍历链表直到找到 "3"。这是否意味着我们仍然有 O(1) 的额外空间？还是说它意味着完全不同的事情？如果我说得一团糟，请原谅。我有点困惑。

- coder123

8

o(1)的空间复杂度意味着你使用的内存量是恒定的，不会取决于正在处理的数据。更多信息请参见此处链接。 - Rodrigo Gonzalez

1

@RodrigoGonzalez 这并不是严格正确的。首先，您写的是小o，而不是大O。假设您指的是大O：假设您有一个函数，它接受单个整数输入 n，并且对于偶数 n 使用 10 kB，对于奇数 n 使用 20 kB。这个函数需要 O（1） 空间，但它肯定不需要恒定数量的空间。这与常量空间不同，后者表示恒定的上限，而不是恒定的数量。 - ubadub

3个回答

-1

这仅仅是程序使用的内存量。也就是算法完成其执行所需的主内存与输入大小相关的数量。

空间复杂度(s(P))是指算法在完成其执行时占用的总空间，与输入大小有关。它包括常数空间和辅助空间。

s(P) = 常数空间 + 辅助空间

常数空间是算法固定的部分，通常等于输入和局部变量使用的空间。辅助空间是算法使用的额外/临时空间。

- Suresh P

-3

假设我创建了一个具有固定大小的数据结构，无论对该数据结构进行什么操作，它的大小始终保持不变。因此，在该数据结构上执行的操作是O(1)。

举个例子，假设我有一个固定大小为100的数组。无论我进行什么操作，无论是从数组中读取还是更新元素，该操作在数组上都是O(1)的。数组的大小（因此使用的内存量）不会改变。

另一个例子，假设我有一个LinkedList，我向其中添加元素。每次向LinkedList添加元素时，这是对列表的O(N)操作，因为我正在增加用于保存所有元素的内存量。

希望这能帮到你！

- Matthew S

这是一个非常糟糕的例子。虽然C数组在应用操作于其成员时不会改变大小，但其他语言并非如此。 - symcbean

我明白，这个特定的例子适用于C语言，可能不适用于其他语言的实现。一旦我有时间，我会在我的解释中添加附录。感谢您的输入@symcbean。 - Matthew S

4

“O(1)”并不意味着一个函数必须对所有的输入使用相同的固定大小，它只需要对所有输入保持一个恒定的上限（在空间方面）。例如，假设你有一个接受单个整数输入“n”的函数，并且它对于偶数“n”使用10 kB，对于奇数“n”使用20 kB。这个函数占用“O(1)”的空间，但它显然并没有使用一个固定大小。然而，上限是固定的，为20 kB。 - ubadub

VLQ队列的审核者请注意：错误答案并不等同于非常低质量。请在此投票“看起来没问题”。 - EJoshuaS - Stand with Ukraine

哦，伙计，我回顾了一下我之前的回答，然后看了看你发布的帖子@EJoshuaS-StandwithUkraine，真是让我开怀大笑。我同意这是一个“如何不去思考O(1)”的例子，虽然它显然是错误的，但本身还是非常有价值的。 - Matthew S

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

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

- Ajay Kumar · Accepted Answer

为了回答你的问题，如果你有一个遍历算法可以通过分配单个指针来遍历列表，那么该遍历算法被认为具有O(1)的空间复杂度。另外，假设该遍历算法需要不止1个而是1000个指针，则空间复杂度仍然被认为是O(1)。

但是，如果由于某种原因，算法在遍历大小为N的列表时需要分配'N'个指针，即，对于遍历3个元素的列表，它需要分配3个指针，对于10个元素的列表，它需要分配10个指针，对于1000个元素的列表，它需要分配1000个指针等等，则该算法被认为具有O(N)的空间复杂度。即使'N'非常小，例如：N=1，这也是正确的。

总之，以上两个例子可以总结为：O(1)表示使用恒定的空间：无论列表大小如何，算法分配的指针数量相同。相反，O(N)表示线性空间使用：随着输入大小的增加，算法的空间使用量呈线性增长。