为什么根据维基百科，冒泡排序的总 space 复杂度为 O(1)？
Why is the total space complexity of bubble sort O(1) according to Wikipedia?
基于This article on GeeksforGeeks and the questions posted on StackExchange and Quroa，算法的space复杂度是解决一个问题所需要的space，包括输入所需要的space，以及auxiliary space 是算法为了解决问题除了输入本身之外还需要的任何额外存储。
现在我知道冒泡排序的辅助 space 是 O(1) 因为它只需要一个变量来跟踪我们在列表排序时看到的交换次数（如果我错了请纠正我），但是为什么 Wikipedia 说冒泡排序的总 space 复杂度也是 O(1)？
考虑到输入本身，它不应该是 O(n) 吗？
术语space complexity定义了算法占用的额外内存量。如果你需要分配一个大小为 N 的数组，这意味着你的算法需要 O(N) 额外的 space 或更具体的辅助 space.
但是在冒泡排序的情况下，我们只能使用单个变量（用于交换目的）来实现。
所以总体 space 复杂度为 O(N)，其中包括您的输入，总体辅助 space 复杂度为 O(1)
在 overall space complexity 的维基百科中，它定义了辅助 space。
why does Wikipedia say that the total space complexity of the bubble sort is O(1) as well?
抓得好！同时进行了更正。它现在表示总 space 复杂度为 O(n)。引用自右侧摘要面板：
Worst-case space complexity O() total, O(1) auxiliary
所以：
- 输入的 space 复杂度为 O()
- 另外算法=辅助需要O(1)space
- 总共space使用了输入和辅助space，所以O()+O(1) = O()
基于This article on GeeksforGeeks and the questions posted on StackExchange and Quroa，算法的space复杂度是解决一个问题所需要的space，包括输入所需要的space，以及auxiliary space 是算法为了解决问题除了输入本身之外还需要的任何额外存储。
现在我知道冒泡排序的辅助 space 是 O(1) 因为它只需要一个变量来跟踪我们在列表排序时看到的交换次数（如果我错了请纠正我），但是为什么 Wikipedia 说冒泡排序的总 space 复杂度也是 O(1)？
考虑到输入本身，它不应该是 O(n) 吗？
术语space complexity定义了算法占用的额外内存量。如果你需要分配一个大小为 N 的数组，这意味着你的算法需要 O(N) 额外的 space 或更具体的辅助 space.
但是在冒泡排序的情况下，我们只能使用单个变量（用于交换目的）来实现。
所以总体 space 复杂度为 O(N)，其中包括您的输入，总体辅助 space 复杂度为 O(1)
在 overall space complexity 的维基百科中，它定义了辅助 space。
why does Wikipedia say that the total space complexity of the bubble sort is O(1) as well?
抓得好！同时进行了更正。它现在表示总 space 复杂度为 O(n)。引用自右侧摘要面板：
Worst-case space complexity O() total, O(1) auxiliary
所以：
- 输入的 space 复杂度为 O()
- 另外算法=辅助需要O(1)space
- 总共space使用了输入和辅助space，所以O()+O(1) = O()