为什么下面的算法是O(1)space？
Why is the following algorithm O(1) space?
输入：一个正整数列表，其中一个条目恰好出现一次，所有其他条目恰好出现两次（例如 [1,3,2,5,3,4,1,2,4]）
输出：唯一条目（上例中为 5）
下面的算法应该是 O(m) 时间和 O(1) space 其中 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)) 位，所以我认为 space 复杂度应该至少为 O(log(m)).
您的分析肯定是一个正确答案，尤其是在像 Python 这样可以优雅地处理任意大数字的语言中。
在考虑 space 和时间复杂度时，清楚您要衡量的内容很重要。一个合理的假设可能是整数的大小是恒定的（例如，您使用的是 64 位整数）。那样的话，space复杂度肯定是O(1)，但是时间复杂度还是O(m)。
现在，您还可以争辩说，使用固定大小的整数意味着您在 m 的大小上有一个恒定的上限，所以时间复杂度可能也是 O(1)。但在大多数需要分析此类算法的 运行 时间的情况下，您可能对长度为 10 的列表与长度为 10 亿的列表之间的差异非常感兴趣。
我想说的是，在分析 space 和时间复杂度时，澄清和陈述您的假设很重要。在这种情况下，我假设我们有一个固定大小的整数和一个比最大整数值小得多的 m 值。在那种情况下，O(1) space 和 O(m) 时间可能是最好的答案。
编辑（基于其他答案中的讨论）
因为所有 m 给你的是 下限 没有列表中的最大值，你真的不能提供最坏情况的估计space。 IE。列表中的数字可以任意大。要对该算法的 space 复杂度有任何合理的回答，您 需要 对输入值的最大大小做出一些假设。
(space/time)复杂度分析通常应用于更高层次的算法。虽然您可以下降到特定的语言实现级别，但它可能并非在所有情况下都有用。
您的分析既正确又可能错误。它适用于当前的 cpython 实现，其中整数没有最大值。如果您的所有整数都相对较小并且适合小数字的特定实现情况，那也没关系。
但它不一定对 python 的所有其他实现都有效。例如，您可以有一个优化实现，它计算出 intlist 不再使用，而不是使用 unique_val，它重用已消耗的列表元素的 space。 （基本上将此函数转换为 space 优化的 reduce 调用）
然后，我们甚至可以讨论 space 使用分配整数的 GC 语言的复杂性吗？您对复杂性的分析是错误的，因为 a ^= b 将为大值 b 分配新内存，其大小取决于系统、体系结构、python 版本和运气。
不过你原来的问题是"Why is the following algorithm O(1) space?"。如果您查看算法本身并假设您有一些任意的最大整数限制，或者您的语言可以表示有限 space 中的任何数字，那么答案是肯定的。具有这些条件的算法本身使用常量 space.
算法的复杂性始终取决于您使用的机器型号（= 平台）。例如。我们经常说 IEEE 浮点数的乘法和除法具有 运行 时间复杂度 O(1) - 情况并非总是如此（例如在没有 FPU 的 8086 处理器上）。
对于上述算法，space 复杂度 O(1) 仅在您的输入列表没有元素 > 2147483647 (= sys.maxint) 时成立。通常，python 将整数存储为带符号的 32 位值。对于这些数据类型，您的处理器已经在硬件中实现了所有相关操作，并且通常只需要固定数量的时钟周期（在大多数情况下只有一个）来执行它们（= 运行-时间复杂度 O(1)）并且只占用恒定数量的内存地址（只有一个）来存储结果（= space 复杂度 O(1)).
但是，如果您的输入超过 2147483647，python 通常使用软件实现的数据类型来存储这些大整数。对这些的操作不再是 O(1)，它们需要的不仅仅是常量 O(1) space.
输入：一个正整数列表，其中一个条目恰好出现一次，所有其他条目恰好出现两次（例如 [1,3,2,5,3,4,1,2,4]）
输出：唯一条目（上例中为 5）
下面的算法应该是 O(m) 时间和 O(1) space 其中 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)) 位，所以我认为 space 复杂度应该至少为 O(log(m)).
您的分析肯定是一个正确答案，尤其是在像 Python 这样可以优雅地处理任意大数字的语言中。
在考虑 space 和时间复杂度时，清楚您要衡量的内容很重要。一个合理的假设可能是整数的大小是恒定的（例如，您使用的是 64 位整数）。那样的话，space复杂度肯定是O(1)，但是时间复杂度还是O(m)。
现在，您还可以争辩说，使用固定大小的整数意味着您在 m 的大小上有一个恒定的上限，所以时间复杂度可能也是 O(1)。但在大多数需要分析此类算法的 运行 时间的情况下，您可能对长度为 10 的列表与长度为 10 亿的列表之间的差异非常感兴趣。
我想说的是，在分析 space 和时间复杂度时，澄清和陈述您的假设很重要。在这种情况下，我假设我们有一个固定大小的整数和一个比最大整数值小得多的 m 值。在那种情况下，O(1) space 和 O(m) 时间可能是最好的答案。
编辑（基于其他答案中的讨论）
因为所有 m 给你的是 下限 没有列表中的最大值，你真的不能提供最坏情况的估计space。 IE。列表中的数字可以任意大。要对该算法的 space 复杂度有任何合理的回答，您 需要 对输入值的最大大小做出一些假设。
(space/time)复杂度分析通常应用于更高层次的算法。虽然您可以下降到特定的语言实现级别，但它可能并非在所有情况下都有用。
您的分析既正确又可能错误。它适用于当前的 cpython 实现，其中整数没有最大值。如果您的所有整数都相对较小并且适合小数字的特定实现情况，那也没关系。
但它不一定对 python 的所有其他实现都有效。例如，您可以有一个优化实现，它计算出 intlist 不再使用，而不是使用 unique_val，它重用已消耗的列表元素的 space。 （基本上将此函数转换为 space 优化的 reduce 调用）
然后，我们甚至可以讨论 space 使用分配整数的 GC 语言的复杂性吗？您对复杂性的分析是错误的，因为 a ^= b 将为大值 b 分配新内存，其大小取决于系统、体系结构、python 版本和运气。
不过你原来的问题是"Why is the following algorithm O(1) space?"。如果您查看算法本身并假设您有一些任意的最大整数限制，或者您的语言可以表示有限 space 中的任何数字，那么答案是肯定的。具有这些条件的算法本身使用常量 space.
算法的复杂性始终取决于您使用的机器型号（= 平台）。例如。我们经常说 IEEE 浮点数的乘法和除法具有 运行 时间复杂度 O(1) - 情况并非总是如此（例如在没有 FPU 的 8086 处理器上）。
对于上述算法，space 复杂度 O(1) 仅在您的输入列表没有元素 > 2147483647 (= sys.maxint) 时成立。通常，python 将整数存储为带符号的 32 位值。对于这些数据类型，您的处理器已经在硬件中实现了所有相关操作，并且通常只需要固定数量的时钟周期（在大多数情况下只有一个）来执行它们（= 运行-时间复杂度 O(1)）并且只占用恒定数量的内存地址（只有一个）来存储结果（= space 复杂度 O(1)).
但是，如果您的输入超过 2147483647，python 通常使用软件实现的数据类型来存储这些大整数。对这些的操作不再是 O(1)，它们需要的不仅仅是常量 O(1) space.