lc203 递归写法复杂度分析

Question

对于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)。不知道对不对。
另外，对于一般的递归问题，时间/空间复杂度怎么分析呢？
谢谢

Answer 1

liuyubobobo 2019-11-15 06:16:38

对的。

通常一个递归算法，空间复杂度很好分析，就是递归深度 + 使用的辅助空间大小。在这个例子中，辅助空间大小是 O(1) 的，递归深度是 O(n) 的，所以整体是 O(n)。

对于时间复杂度的分析，从通常面试来讲，我认为需要掌握的是：

1）如果很容易转成非递归算法的话，和非递归算法的时间复杂度是等价的。正确的递归转非递归或这非递归转递归，不会产生复杂度的变化。

2）一些特殊的结构上的递归算法，一般都是计算机的常事。比如基于树结构的递归算法，图的 DFS 等等。

3）一些特殊的算法，时间复杂度的分析方式相对比较固定，比如归并排序，快速排序的分析方式，或者回溯法，动态规划的分析方式。

而更加通用的递归算法的时间复杂度分析，是一个很理论化的内容。通常被一个称为“主定理”的方式所概括。一般的面试，考研等场景，是不可能考主定理的。这已经远远超过这门课程的教学目标了。如果对主定理感兴趣，可以在网上搜索更多资料学习。在《算法导论》上，就有专门的一节介绍主定理。

继续加油！：）

• 提问者 Y1ng #1

  非常感谢！

• 提问者 Y1ng #2

  对于第一条中“很容易转成非递归算法”该怎么理解呢？
  有没有一个比较确切的标准？谢谢老师。

• liuyubobobo 回复 提问者 Y1ng #3

  没有确切的标准。这是一个主观的说法，就是一看就能转成非递归的算法。一般在我看来，线性的递归算法都是很容易转成非递归的。

点开查看后面1条评论