Space 缩小输入时的复杂度
Space complexity when making input smaller
假设您要查找一个数组中的所有重复项，并且您必须在 O(1) space 和 O(N) 时间内完成此操作。
像这样的算法会有 O(N) space:
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) space 还是 O(N) space:
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|，但最终我认为它仍在为 seen 分配 |arr| space。
每当您尝试进行时间和 space 复杂性分析时，请考虑一个最可能会破坏您的程序的测试用例。
您的 space 复杂度为 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 了解更多详情。
为了确定 space 的复杂性，您必须了解 pop 的实现方式以及 Python 管理内存的方式。为了让您的算法使用常量 space，arr 必须释放弹出项目使用的内存，并且 seen 必须能够重用该内存。但是，Python 可能 的大多数实现不支持该级别的共享。特别是，pop 不会释放任何内存；它将防止将来需要它的可能性，而不必要求恢复记忆。
假设您要查找一个数组中的所有重复项，并且您必须在 O(1) space 和 O(N) 时间内完成此操作。
像这样的算法会有 O(N) space:
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) space 还是 O(N) space:
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|，但最终我认为它仍在为 seen 分配 |arr| space。
每当您尝试进行时间和 space 复杂性分析时，请考虑一个最可能会破坏您的程序的测试用例。
您的 space 复杂度为 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 了解更多详情。
为了确定 space 的复杂性，您必须了解 pop 的实现方式以及 Python 管理内存的方式。为了让您的算法使用常量 space，arr 必须释放弹出项目使用的内存，并且 seen 必须能够重用该内存。但是，Python 可能 的大多数实现不支持该级别的共享。特别是，pop 不会释放任何内存；它将防止将来需要它的可能性，而不必要求恢复记忆。