O（1）空间复杂度是多少？ [英] What is O(1) space complexity?

问题描述

我很难理解什么是O（1）空间复杂度。我知道这意味着算法所需的空间不会随着输入或我们正在使用算法的数据大小而增加。但是，这到底是什么意思？

I am having a hard time understanding what is O(1) space complexity. I understand that it means that the space required by the algorithm does not grow with the input or the size of the data on which we are using the algorithm. But what does it exactly mean?

如果我们在链接列表上使用算法，例如1-> 2-> 3-> 4，则遍历列表以达到 3，我们声明一个临时指针。遍历列表直到达到3。这是否意味着我们还有O（1）多余的空间？或者这意味着完全不同的东西。很抱歉，如果这根本没有意义。我有点困惑。

If we use an algorithm on a linked list say 1->2->3->4, to traverse the list to reach "3" we declare a temporary pointer. And traverse the list until we reach 3. Does this mean we still have O(1) extra space? Or does it mean something completely different. I am sorry if this does not make sense at all. I am a bit confused.

推荐答案

要回答您的问题，如果您有遍历列表的遍历算法，该算法分配了一个这样做的指针，遍历算法被认为是O（1）空间复杂度。另外，假设遍历算法不需要1而是1000个指针，那么空间复杂度仍被认为是O（1）。

To answer your question, if you have a traversal algorithm for traversing the list which allocate a single pointer to do so, the traversal algorithms is considered to be of O(1) space complexity. Additionally, let's say that traversal algorithm needs not 1 but 1000 pointers, the space complexity is still considered to be O(1).

但是，如果出于某种原因而说该算法在遍历大小为N的列表时需要分配 N个指针，即，在遍历3个元素的列表时需要分配3个指针，对于10个元素的列表需要分配10个指针，对于1000个元素的列表需要1000个指针依此类推，则认为该算法的空间复杂度为O（N）。即使'N'非常小，例如N = 1，也是这样。

However, if let's say for some reason the algorithm needs to allocate 'N' pointers when traversing a list of size N, i.e., it needs to allocate 3 pointers for traversing a list of 3 elements, 10 pointers for a list of 10 elements, 1000 pointers for a list of 1000 elements and so on, then the algorithm is considered to have a space complexity of O(N). This is true even when 'N' is very small, eg., N=1.

总结以上两个示例，O（1）表示常量空间的使用：无论列表大小如何，该算法都会分配相同数量的指针。相反，O（N）表示线性空间使用：算法空间使用随输入大小而增长。

To summarise the two examples above, O(1) denotes constant space use: the algorithm allocates the same number of pointers irrespective to the list size. In contrast, O(N) denotes linear space use: the algorithm space use grows together with respect to the input size.

这篇关于O（1）空间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！