Java中传递数组的时间和空间复杂度

Question

假设我有一个递归函数，它在具有n节点和高度的完美平衡的二叉树上工作，并log(n)在树的根部调用下面的函数。

void printPaths(TreeNode root, int[] array, int depth){
    if (root == null){
        print array;
    }
    array[depth] = root.data;
    printPaths(root.left, array, depth + 1);
    printPaths(root.right, array, depth + 1);
}

array = new int[depthOfTree]
printPaths(root, array, 0);

让数组为长度log(n)（它将沿树的路径存储值）。我知道递归调用堆栈将是 max height log(n)。我不确定的是 Java 的“按值传递”性质和 Java 垃圾收集如何影响时间和空间复杂性。

1) 将数组传递给递归调用的时间复杂度是多少？如果 Java 是“按值传递”，那么O(log(n))在开始任何函数执行之前，每个递归调用是否都只是简单地复制数组？

2) 任一时刻在内存中浮动的这些数组副本的上限是多少？我的倾向是说O(log(n))。这是否意味着空间复杂度是O(log(n)log(n))？我在一本书中读到“空间复杂度是O(log(n))因为算法会递归O(log(n))次数，并且路径参数O(log(n))在递归过程中只在空间分配一次”。

Answer 1

1) 将数组传递给递归调用的时间复杂度是多少？如果 Java 是“按值传递”，那么在开始任何函数执行之前，每个递归调用是否都需要 O(log(n)) 来简单地复制数组？

只是 O(1)。所述参考是按值传递。数组是引用类型（即使数组的元素类型是值类型，例如 for int[]）。

所以array表达式的值不是数组对象本身——它只是一个引用。

2) 任一时刻在内存中浮动的这些数组副本的上限是多少？

正是 1，出于同样的原因。你有一个数组，堆栈中的每一层都有一个对它的引用。

每个递归步骤占用的唯一额外内存是堆栈上局部变量值的足够空间......这是每次调用的恒定空间量。对于 O(log(N)) 的深度，这也意味着 O(log(N)) 的空间复杂度。