lc203 递归写法复杂度分析
来源：5-3 设立链表的虚拟头结点 Remove Linked List Elements
Y1ng
2019-11-15
对于lc203的递归写法
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
head.next = removeElements(head.next, val);
return (head.val == val)? head.next : head;
}
}
请问下时间空间复杂度分别为多少呢？
我的理解是两遍遍历所以时间是O(n)，而递归过程我理解像压栈和出栈的过程，所以空间是O(n)。不知道对不对。
另外，对于一般的递归问题，时间/空间复杂度怎么分析呢？
谢谢
写回答
1回答
-
对的。
通常一个递归算法，空间复杂度很好分析，就是递归深度 + 使用的辅助空间大小。在这个例子中，辅助空间大小是 O(1) 的，递归深度是 O(n) 的，所以整体是 O(n)。
对于时间复杂度的分析，从通常面试来讲，我认为需要掌握的是：
1）如果很容易转成非递归算法的话，和非递归算法的时间复杂度是等价的。正确的递归转非递归或这非递归转递归，不会产生复杂度的变化。
2）一些特殊的结构上的递归算法，一般都是计算机的常事。比如基于树结构的递归算法，图的 DFS 等等。
3）一些特殊的算法，时间复杂度的分析方式相对比较固定，比如归并排序，快速排序的分析方式，或者回溯法，动态规划的分析方式。
而更加通用的递归算法的时间复杂度分析，是一个很理论化的内容。通常被一个称为“主定理”的方式所概括。一般的面试，考研等场景，是不可能考主定理的。这已经远远超过这门课程的教学目标了。如果对主定理感兴趣，可以在网上搜索更多资料学习。在《算法导论》上，就有专门的一节介绍主定理。
继续加油！：）
142019-11-15
相似问题
关于2-1递归空间复杂度
回答 1
表达式求时间复杂度
回答 1