树问题 - 理解何时实现迭代解决方案和何时实现递归解决方案

Question

我最近在利用业余时间解算法问题，为明年夏季实习面试做准备。目前我正在解决与树有关的问题，我发现对于大多数问题来说，实际编码并不困难，但是我很难理解这些问题的复杂性。我正在解决的一个问题是二叉树的前序遍历，我已经实现了递归和迭代两种方法。然而，迭代方案要慢得多，并且我不明白为什么？以下是我的两种解决方案：

迭代：

public List<Integer> preorder(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();

    if (root == null) return ans;

    stack.push(root);

    while(!stack.isEmpty()) {
        TreeNode node = stack.pop();
        ans.add(node.val);

        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    {

    return ans;
}

递归：

public list<Integer> preorder(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    dfs(root, ans);
    return ans;
}

public void dfs (TreeNode root, List<Integer> ans) {
    if (root == null) return;
    ans.add(root.val);
    dfs(root.left);
    dfs(node.right)
}

据我所见，递归解决方案每次调用有两个分支，如果树是平衡的，则深度为O(log n)，但最坏情况是O(n)，因此时间复杂度将为O(2^n)。我的看法可能完全错误。迭代解决方案具有恒定的推入和弹出时间，因此我的初步直觉是它的时间复杂度为O(n)。如果这些是情况，我无法想象指数解决方案如何运行更快。如果有人能帮助我理解这类问题的复杂性，那将非常感激。

- bh13

---

你测试了多少十亿十亿十亿个节点？O()与算法的渐近行为有关，除非你接近该行为，否则你的算法运行时间与O()性能无关。在你的情况下，你拥有一个托管栈对象或CPU栈，而且你猜怎么着... CPU栈比你的栈快，因为它没有堆分配。 - Ian Mercer

如果你想了解你的代码执行了多少操作，可以添加一个计数器。这个计数器在每种情况下都是相同的，因为你只会访问每个节点一次。 - Ian Mercer

Answer 1

在这两种情况下，时间复杂度都是 O(n) ：您访问每个节点一次，并对每个节点进行恒定数量的操作（将值添加到 ArrayList 或 Stack 中是摊销 O(1)）。

你的迭代解决方案较慢的原因之一可能是使用了 Stack。这个类是同步的（它扩展了 Vector）。在这种情况下，您不需要线程安全性，请考虑将其替换为 ArrayDeque：

Deque<Integer> stack = new ArrayDeque<Integer>();

在这两种情况下，空间复杂度都是 O(n)：迭代解法中的显式栈和递归解法中的隐式调用栈都可以增长到 n（不平衡情况）。

- Alex Filatov

Answer 2

拥有恒定复杂度与指数复杂度并不意味着它更快。它只是关于输入增长时它会变慢的速率的说明。我认为这对于面试和现实世界来说本身就是一个非常有价值的教训，因为最低 O-时间的解决方案通常并不是“最好的”或更实用的。

除了复杂度之外，我可以看出基于堆栈的方法可能会更慢，因为它需要在 stack 上弹出和推入项目，而递归解决方案只需要调用函数。如果没有进行基准测试，我无法确定这一点。

- Evert

---

感谢澄清。O时间复杂度只是衡量算法在输入增大时的扩展性，对吗？在这种情况下，可以说DFS与O(V + E)相比复杂度相对较为相似吗？我只是有些困惑，何时更合适地使用迭代或递归实现算法。 - bh13

@bh13 我的直觉是它们具有相同的复杂度，但是要100％诚实地说，我不能百分之百确定。我从来不擅长这些。 - Evert

回到实际情况，如果输入的规模足够大，递归函数可能会因为栈溢出错误而失败。如果我在现实世界中遇到这种情况，我很可能会选择简单的递归函数，除非输入规模非常大 =) - Evert