英文:
Space complexity of overwriting function input
问题
在我们的函数中，我们通过将输入的排序版本存储在其中来覆盖原始参数nums。
我的问题很简单：覆盖输入是否算作辅助空间占用？更具体地说，我们的函数的辅助空间是O(N)还是O(1)？
我知道这个问题不太复杂，但我无法在任何地方找到明确的答案。我理解sorted()生成并存储了列表的新版本。这样一来，这种操作占用了O(N)的空间，其中N是输入列表的长度。
然而，由于我们正在覆盖已经保存有大小为N的列表的输入，我们是否仍然认为这个操作占用了额外的O(N)空间？
英文:
Suppose we have the function below:
def foo(nums):
nums = sorted(nums)
return nums
In our function, we overwrite our original parameter nums, by storing the sorted version of the input in it.
My question is simple: does overwriting the input count toward auxiliary space occupation? More specifically, is the auxiliary space of our function O(N) or O(1)?
I know this question is not very nuanced, but I cannot find a clear answer anywhere. I understand that sorted() produces and stores a new version of the list. In this way, such an operation occupies O(N) space, where N is the length of the input list.
However, since we are overwriting the input, which already held a list of size N, do we still consider this operation occupying additional O(N) space?
答案1
得分: 2
然而，由于我们正在覆盖输入，这不是Python的工作方式。我们没有覆盖输入。nums是函数范围内输入列表的名称，然后我们将其更改为排序列表的名称。
为了更好地理解Python中名称和值的工作原理，我建议观看这个出色的PyCon演讲。
由于nums后面的列表至少还被方法的调用者引用，它在操作完成之前不能被垃圾回收。
会有一个时刻，新列表和旧列表都共存，因此我们会额外占用O(N)的空间。
Python使用Timsort进行排序，其消耗O(N)的空间复杂度，因此即使使用.sort()进行原地排序，仍会消耗O(N)的空间。
英文:
> However, since we are overwriting the input
This is not how Python works. We're not overriding the input.
nums is a name for the input list within the function scope, and then we change it to be the name for the sorted list.
To better understand how Python names and values work I recommend this excellent PyCon talk.
Since the list behind nums is at least still referenced by the caller of the method, it can not be garbage collected until the operation finishes.
There will be a moment when the new list and the old list both co-exist, thus we take additional O(N) space.
Python uses Timsort for sorting which consumes O(N) space complexity, so even sorting it in place with .sort() still consumes O(N).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论