使输入更小时的空间复杂性

Question

想象一下，你想要找到一个数组中的所有重复项，你必须在O(1)空间和O(N)时间执行此操作。

像这样的算法会有O(N)空间：

def find_duplicates(arr):

    seen = set()
    res = []
    for i in arr:
        if i in seen: res.append(i)
        seen.add(i)
    return res

我的问题是以下算法使用O(1)空间或O(N)空间：

def find_duplicates(arr):

    seen = set()
    res = []
    while arr:
        i = arr.pop()
        if i in seen: res.append(i)
        seen.add(i)
    return res

技术上arr变得更小，|seen|和|arr|的总和将总是小于原始的|arr|，但在一天结束时，我认为它仍然为|arr|分配seen空间。

Answer 1

为了确定空间复杂性，您必须了解pop的实现方式，以及Python如何管理内存。为了使您的算法使用常量空间，arr必须释放弹出项目使用的内存，而seen必须能够重用该内存。但是，Python的大多数实现可能不支持该级别的共享。特别是，pop不会释放任何记忆;它将使它不再需要它在未来，而不是要求回忆。

Answer 2

每当您尝试进行时间和空间复杂性分析时，请考虑一个可能会最大程度地破坏您的程序的测试用例。

你的空间复杂度是O（N）。对于第二个程序，如果您有一个只有1的数字列表。例如：x = [1,1,1,1,1,1,1]。然后你会看到res几乎增长到N的大小。考虑当你拥有所有不同的数字时会发生什么。 x = [1,2,3,4,5,6,7,8]。现在seen增长到N的大小。

考虑到时间复杂性，python列表的pop()函数有时可能是一个问题。查看此post了解更多详情。