如何检查我们代码的 space 复杂度是否为 O(1)

Question

在问题中，据说我们需要以 O(1) space 复杂度编写代码，我看着它感到困惑。有人可以解释一下 space 复杂度这段代码。如果不在 O(1) 内，有什么办法可以改变它吗？

python3

from collections import Counter
def duplicates(arr, n): 
    r=[]
    dic=Counter(arr)
    for i in dic:
        if dic[i]>1:
            r.append(i)
    if r:
        r.sort()
        return r
    else:
        r.append(-1)
        return r

Answer 1

Space复杂度是多少space渐近使用（当N变得非常大时）

O(1) space 复杂性通常由变量和大小不变的数组组成。

您的代码复杂度为 O(N) space，因为数组 r 随着 N 的大小而增长。

Answer 2

好吧，如果你不使用额外的数据结构，比如除了问题中的数组，那么你的 space 复杂度是恒定的 O(1) 否则它可能不是。

问题是您是否引入了任何额外的集合数组来保存您的数据或结果？如果否，则您以常数 space O(1) 求解它，如果是，则它不是常数 space.

您必须根据您引入的额外数组计算 space 复杂度。

如何检查我们代码的 space 复杂度是否为 O(1)

how to check the space complexity of our code is O(1) or not

python-3.x

space-complexity