python-3.x - 如何检查我们代码的空间复杂度是否为 O(1)

Question

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

蟒蛇3

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

标签： python-3.xspace-complexity

Answer 1

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

O(1) 空间复杂度通常由具有恒定大小的变量和数组组成。

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