1

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))空间分配一次”。

4

2 回答 2

5

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

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

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

2）任何时候这些数组副本中有多少在内存中浮动的上限是多少？

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

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

于 2013-07-24T05:17:41.137 回答
1

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

Java 不复制数组。在 Java 中，您将 Object 的引用作为方法中的参数传递。因此，当 Object 的数据发生变化时，它会反映到引用它的所有引用中。

于 2013-07-24T05:19:32.600 回答