java - 如何计算用于在调用堆栈上保存输入以进行递归的空间

Question

假设我有一个功能

public void dfs(int[] a, int[] b, int count){
     if(count == 0) return;
     dfs(a, b, count-1);
     return;
}

我想计算dfs的空间复杂度。调用堆栈的深度将被计算在内。然后在每个调用堆栈上，我需要存储 a 和 b 的副本。基于这个推理，我倾向于得出空间复杂度为：O((a.length + b.length) * count) 的结论。但是，我认为当 Java 将对象传递给函数时，它只是将 a、b 的地址的副本传递给给定函数。因此，我认为每个调用堆栈都不需要 O(a.length + b.length) 空间来保存输入。它只需要存储a和b地址的空间，这应该是常数。这个对吗？

标签： javaalgorithmtime-complexityspace-complexity

Answer 1

你最后的说法是正确的。不制作输入数组的副本，因此唯一需要的额外空间是堆栈深度的线性：O(count)。