Space 递归创建对象的复杂性

Question

checkIfBalanced() 下面代码中的方法 returns 如果树是平衡的，则为真，否则为假。但是在每次递归中它都会创建 TreeData 对象。在我看来 space 复杂度为 O(1)，因为在弹出每个堆栈帧后，在该堆栈帧上创建的对象的引用将丢失并被垃圾收集。我对吗？

请注意：

我不是在寻找对 improve/change 我的代码的建议。以下代码示例是为问我的问题量身定制的。
此外，please ignore space-complexity adding stack frames。我正在寻找创建的 'TreeData' 个对象的 space 复杂度。在我看来，在任何时候都只有 3 个 TreeData 对象。这就是我要验证的。谢谢

   private static class TreeData {
        private int height;
        private boolean isBalanced; 

        TreeData(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }

    public boolean checkIfBalanced() {
        if (root == null) {
            throw new IllegalStateException();
        }
        return checkBalanced(root).isBalanced;
    }

    public TreeData checkBalanced(TreeNode node) {
        if (node == null) return new TreeData(-1, true);

        TreeData tdLeft = checkBalanced(node.left);
        TreeData tdRight = checkBalanced(node.right);

        if (tdLeft.isBalanced && tdRight.isBalanced && Math.abs(tdLeft.height - tdRight.height) <= 1) {
            return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, true);
        } 

        return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, false);
    }

Answer 1

However in each recursion it creates TreeData object.

不正确。您仅在递归的基本情况下创建新的 TreeData 对象。如果您担心这一点，为什么不在可以使用的 class 中声明一次静态最终 TreeData 实例。毕竟，您从该节点传播回来的唯一东西是它的 isBalanced 布尔值。

如果您将方法签名更改为 return 布尔值，您也可以直接传播布尔值。

Answer 2

您在这里没有使用尾递归，而是在向上递归树时构建堆栈帧。公平地说，计算那些堆栈帧。如果您的树是平衡的，那么您将在递归时创建 log n 个堆栈帧。在最坏的情况下，对于一棵完全退化的树，您可能有多达 n 个堆栈帧。

Answer 3

In my opinion space complexity is O(1) as after each stack frame is popped, the reference of the object created on that stack frame is lost and garbage collected. Am I right ?

不，你的假设是错误的。 Ray Toal 对此做了非常漂亮的解释。在递归的任何时候，您必须计算所有保存到内存中的内部堆栈帧，因为 Space-Complexity 考虑了所有辅助 space（额外的 space）以及输入（这里不强调）

接下来，

I am looking for space complexity of number 'TreeData' objects created.

递归程序消耗的最大space 与构造的递归树的最大深度成正比。递归树的最大深度定义为树中最长路径的长度。

对于给定的程序，程序将从树的根开始，首先开始创建左边的sub-tree，然后检查right-subtree。最后，它将 return 最长路径的长度以及树是否平衡。

It looks to me that at any point there would be only 3 TreeData objects. That's what I want to verify.

没有，在任何特定的执行时间，首先验证所有的左子树，然后验证right-subtrees，所以内存中的TreeData的objects的数量将只有1. 每次都会检查它是左还是右child。因此，所有这些（log n --- 在平衡树的情况下，或 n --- 在退化树的情况下）节点除了一个将继续堆叠在内存中。在某个特定的时刻，只有1个TreeDataobject处于活动状态，其他的会暂停并堆放在内存中等待轮到它们弹出。

Space 递归创建对象的复杂性

Space complexity on creating an object on recursion

algorithm

recursion

space-complexity