什么是 O(1) space 复杂度？
What is O(1) space complexity?
我很难理解什么是 O(1) space 复杂度。我理解这意味着算法所需的 space 不会随着输入或我们使用该算法的数据的大小而增长。但这到底是什么意思？
如果我们在链表上使用算法，比如 1->2->3->4，为了遍历链表到达“3”，我们声明了一个临时指针。并遍历列表直到我们到达 3。这是否意味着我们还有 O(1) 额外的 space？或者它意味着完全不同的东西。如果这根本没有意义，我很抱歉。我有点困惑。
假设我创建了一些具有固定大小的数据结构，无论我对数据结构做什么，它总是具有相同的固定大小。因此，对该数据结构执行的操作是 O(1).
举个例子，假设我有一个固定大小为 100 的数组。我执行的任何操作，无论是从数组读取还是更新元素，该操作对数组的复杂度为 O(1)。数组的大小（以及它使用的内存量）没有改变。
另一个例子，假设我有一个 LinkedList，我向其中添加了元素。每次我向 LinkedList 添加一个元素时，这就是对列表的 O(N) 操作，因为我增加了将所有元素保存在一起所需的内存量。
希望对您有所帮助！
为了回答你的问题，如果你有一个遍历列表的遍历算法，它分配一个指针来这样做，那么这个遍历算法被认为是 O(1) space 复杂度。另外，假设遍历算法需要的不是1个而是1000个指针，space复杂度仍然被认为是O(1)。
但是，如果说由于某种原因，算法在遍历大小为 N 的列表时需要分配 'N' 个指针，即它需要分配 3 个指针来遍历 3 个元素的列表，10 个指针对于 10 个元素的列表，对于 1000 个元素的列表有 1000 个指针等等，那么该算法被认为具有 O(N) 的 space 复杂度。即使 'N' 非常小也是如此，例如 N=1.
总结上面两个例子，O(1)表示常量space使用：无论列表大小如何，算法分配相同数量的指针。相反，O(N) 表示线性 space 使用：算法 space 使用随输入大小一起增长。
它只是一个程序使用的内存量。相对于输入大小，算法完成其执行所需的计算机内存量，即主内存。
算法的 Space Complexity(s(P)) 是算法完成其执行相对于输入大小的总 space。它包括 Constant space 和 Auxiliary space.
S(P) = Constant space + Auxiliary space
常量 space 是为该算法固定的常量，通常等于 space 用于输入和局部变量。辅助Space是算法使用的extra/temporaryspace。
我很难理解什么是 O(1) space 复杂度。我理解这意味着算法所需的 space 不会随着输入或我们使用该算法的数据的大小而增长。但这到底是什么意思？
如果我们在链表上使用算法，比如 1->2->3->4，为了遍历链表到达“3”，我们声明了一个临时指针。并遍历列表直到我们到达 3。这是否意味着我们还有 O(1) 额外的 space？或者它意味着完全不同的东西。如果这根本没有意义，我很抱歉。我有点困惑。
假设我创建了一些具有固定大小的数据结构，无论我对数据结构做什么，它总是具有相同的固定大小。因此，对该数据结构执行的操作是 O(1).
举个例子，假设我有一个固定大小为 100 的数组。我执行的任何操作，无论是从数组读取还是更新元素，该操作对数组的复杂度为 O(1)。数组的大小（以及它使用的内存量）没有改变。
另一个例子，假设我有一个 LinkedList，我向其中添加了元素。每次我向 LinkedList 添加一个元素时，这就是对列表的 O(N) 操作，因为我增加了将所有元素保存在一起所需的内存量。
希望对您有所帮助！
为了回答你的问题，如果你有一个遍历列表的遍历算法，它分配一个指针来这样做，那么这个遍历算法被认为是 O(1) space 复杂度。另外，假设遍历算法需要的不是1个而是1000个指针，space复杂度仍然被认为是O(1)。
但是，如果说由于某种原因，算法在遍历大小为 N 的列表时需要分配 'N' 个指针，即它需要分配 3 个指针来遍历 3 个元素的列表，10 个指针对于 10 个元素的列表，对于 1000 个元素的列表有 1000 个指针等等，那么该算法被认为具有 O(N) 的 space 复杂度。即使 'N' 非常小也是如此，例如 N=1.
总结上面两个例子，O(1)表示常量space使用：无论列表大小如何，算法分配相同数量的指针。相反，O(N) 表示线性 space 使用：算法 space 使用随输入大小一起增长。
它只是一个程序使用的内存量。相对于输入大小，算法完成其执行所需的计算机内存量，即主内存。
算法的Space Complexity(s(P)) 是算法完成其执行相对于输入大小的总 space。它包括 Constant space 和 Auxiliary space.
S(P) = Constant space + Auxiliary space
常量 space 是为该算法固定的常量，通常等于 space 用于输入和局部变量。辅助Space是算法使用的extra/temporaryspace。