Space 复杂性 (Python)
Space Complexity (Python)
我有一个问题，假设 gdc(i, n) 时间和 space 复杂度是 O(1)，这个函数的 space 复杂度是多少？
由于 for 循环，时间复杂度为 O(n)。
Space 复杂度如何？答案是 O(1) 但我不明白为什么...导致 for 循环占用 n space 所以不应该是 O(n) 吗？
def gcd_fun(n):
for i in range(1, n+1):
result += gcd(i, n)
return result
这取决于您的 python 版本。如果您使用 python 2，它会为范围函数创建列表。分别地，list需要O(n)的内存复杂度。否则，如果您使用 python 3，它会创建生成器。
更新：正如 Vineeth 所说，范围不是迭代器。抱歉造成误导。
根据文档：
The advantage of the range type over a regular list or tuple is that a range object will always take the same (small) amount of memory, no matter the size of the range it represents (as it only stores the start, stop and step values, calculating individual items and subranges as needed).
我有一个问题，假设 gdc(i, n) 时间和 space 复杂度是 O(1)，这个函数的 space 复杂度是多少？ 由于 for 循环，时间复杂度为 O(n)。 Space 复杂度如何？答案是 O(1) 但我不明白为什么...导致 for 循环占用 n space 所以不应该是 O(n) 吗？
def gcd_fun(n):
for i in range(1, n+1):
result += gcd(i, n)
return result
这取决于您的 python 版本。如果您使用 python 2，它会为范围函数创建列表。分别地，list需要O(n)的内存复杂度。否则，如果您使用 python 3，它会创建生成器。
更新：正如 Vineeth 所说，范围不是迭代器。抱歉造成误导。
根据文档：
The advantage of the range type over a regular list or tuple is that a range object will always take the same (small) amount of memory, no matter the size of the range it represents (as it only stores the start, stop and step values, calculating individual items and subranges as needed).