元素跨数据结构转移未新增对象时空间复杂度是否变化？附函数复杂度疑问

问题1：元素在数据结构间转移且未新增对象时，空间复杂度是否变化？ #

这要分两种维度来看：

• 若关注总空间（输入数据+算法临时空间）：由于没有创建新对象，只是转移已有元素的存储位置，总空间确实保持恒定，不会变化。
• 但算法分析中默认的空间复杂度指的是额外空间复杂度——即算法运行时，除输入本身外额外申请的存储空间大小：
  • 如果是原地转移（比如在原数组内调整元素，未使用新容器），额外空间复杂度为O(1)；
  • 如果转移到新容器（比如从数组移到集合），哪怕没有新增对象，新容器的空间属于额外申请，最坏情况下其规模和输入规模n成正比，此时额外空间复杂度为O(n)。

问题2：查找首个重复值的函数空间复杂度判断是否正确？ #

你的判断错误，该函数的空间复杂度是O(n)，而非O(1)。

原因在于：算法空间复杂度分析的是最坏情况下的额外空间占用。你用到的found集合属于额外申请的空间，原数组是输入数据，其空间不计入额外空间。当数组中无重复元素时，found集合会存储所有n个元素，此时额外空间的规模与输入n成正比，因此空间复杂度为O(n)。你提到的“总空间恒定”不是空间复杂度分析的核心维度，额外空间的增长趋势才是关键。

你的函数代码： #

# o(n) time.
# o(1) space or o(n) space?
def firstDuplicateValue(array):
    found = set()
    while len(array) > 0:
        x = array.pop(0) #we remove elements from the array as we add them to the set
        if x in found:
            return x
        else:
            found.add(x)
    return -1

内容的提问来源于stack exchange，提问作者Remixt