递归函数的空间复杂度分析
在我们的计算机科学课程中，我们没有介绍如何分析空间复杂度。不过，我们的任务是实现一个 $\Theta(n)-time$ 算法来反转单链表，最大 $O(1)-space$（除了实际数组之外）。
这是我在 Python 中的实现：
#x0.next = x1
def invert(x0,x1):
next = x1.next
x1.next = x0
if next is None:
return x1
else:
invert(x1,next)
def invertSLinkyList(head):
firstNext = head.next
head.next = None
x = 0
x = invert(head,firstNext)
return x
给出一个快速的口头描述：本质上，我们迭代每个节点 (x0) 并将其下一个 (x1) 设置为前一个节点。然后，我们在其下一个(x1.next)上递归地调用原始下一个(x1)，直到到达结束节点（其中next = None）如果我们返回这个节点作为新的头。
我已经将其时间复杂度分析为 $\Theta(n)$，基于：
- 每次调用在恒定时间内创建 1 个子注释
- 当代码迭代整个列表时，我们创建 n 个子注释。
- “合并”需要 $O(1)$
我的问题是；我该如何分析它的空间复杂度？
OBS：请注意，这不是评分作业。这是我每周训练的一部分。
In our CS course, we haven't covered how to analyse space complexity. We have though, been given the task of implementing an $\Theta(n)-time$ algorithm for reversing a singly linked list, with a maximum $O(1)-space$ (besides the actual array).
This is my implementation in Python:
#x0.next = x1
def invert(x0,x1):
next = x1.next
x1.next = x0
if next is None:
return x1
else:
invert(x1,next)
def invertSLinkyList(head):
firstNext = head.next
head.next = None
x = 0
x = invert(head,firstNext)
return x
To give a quick verbal description: Essentially, we iterate through each node (x0) and set its next (x1) to the previous node. We then call this recursively on the original next (x1) on its next (x1.next), until we reach the end node (which has next = None) at which case we return this node as the new head.
I have analysed its time complexity to be $\Theta(n)$ based on:
- Each call creates 1 child note at a constant time
- We create n children as the code iterates through the whole list.
- It takes $O(1)$ to "merge"
My question is then; How do I go about analysing its space complexity?
OBS: Please not that this is not a graded assignment. It is a part of my weekly training exercises.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
为了分析空间复杂度，您需要分析内存量是否依赖于n。换句话说，当您的算法输入大小发生变化时，在这种情况下 LL 的节点数量会影响所使用的空间吗？
在这种情况下，通过使用递归，您可以将帧添加到调用堆栈并以这种方式使用内存。既然您提到您对每个节点进行递归调用，您能推理出空间复杂度吗？这与您的参赛作品有什么关系？
在这种情况下，直到
next为none时才会返回，此时将向调用堆栈添加多少堆栈帧？在这种情况下，n 个帧将被放入调用堆栈中，因此您将获得 O(n) 的空间复杂度
To analyze space complexity, you are analyzing whether the amount of memory is dependent on n. In other words, as your algorithm input size changes, number of nodes for the LL in this case, does that affect the space used?
In this case, by using recursion, you are adding frames to the call stack and using memory that way. Since you mention that you make a recursive call per node, can you reason the space complexity? How does that relate to your entries?
In this case, you won't return until
nextisnone, at that point how many stack frames would be added to the call stack?In this case, n frames would be put on the call stack, therefore you would get a Space complexity of O(n)
求下列代码的时间复杂度和空间复杂度。
def list_sum_recursive(input_list):
# 基本情况
如果 input_list == []:
返回 0
#驱动程序代码
打印（list_sum_recursive（[1,2,3]））
Find the time and space complexity of following code.
def list_sum_recursive(input_list):
# Base case
if input_list == []:
return 0
#Driver Code
print(list_sum_recursive([1, 2, 3]))