python - 为什么下面的算法是 O(1) 空间？

Question

输入:一个正整数列表，其中一个条目恰好出现一次，所有其他条目恰好出现两次(例如 [1,3,2,5,3,4,1,2,4])

输出:唯一条目(上例中为 5)

下面的算法应该是 O(m) 时间和 O(1) 空间，其中 m 是列表的大小。

def get_unique(intlist):
    unique_val = 0
    for int in intlist:
        unique_val ^= int
    return unique_val

我的分析:给定一个长度为 m 的列表，输入列表中将有 (m + 1)/2 个唯一的正整数，因此列表中可能的最小最大整数将为 (m+1)/2。如果我们假设这是最好的情况，那么在进行 XOR 和时，变量 unique_val 将需要内存中的 ceiling(log((m+1)/2)) 位，所以我认为空间复杂度至少应为 O(log(m )).

Answer 1

您的分析肯定是一个正确的答案，尤其是在像 Python 这样可以优雅地处理任意大数字的语言中。

在考虑空间和时间复杂性时，务必清楚您要衡量的是什么。一个合理的假设可能是整数的大小是恒定的(例如，您使用的是 64 位整数)。那样的话，空间复杂度肯定是O(1)，但时间复杂度还是O(m)。

现在，您还可以争辩说，使用固定大小的整数意味着您在 m 的大小上有一个恒定的上限，因此时间复杂度可能也是 O(1)。但在大多数情况下，当您需要分析此类算法的运行时间时，您可能会对长度为 10 的列表与长度为 10 亿的列表之间的差异非常感兴趣。

我想说的是，在分析空间和时间复杂性时，澄清和陈述您的假设很重要。在这种情况下，我假设我们有一个固定大小的整数和一个比最大整数值小得多的 m 值。在那种情况下，O(1) 空间和 O(m) 时间可能是最好的答案。

编辑(基于其他答案中的讨论)

因为所有 m 给你的是一个下限 没有列表中的最大值，你真的不能提供空间的最坏情况估计。 IE。列表中的数字可以任意大。要对该算法的空间复杂度有任何合理的答案，您需要对输入值的最大大小做出一些假设。