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

kx5bkwkv  于 2021-07-06  发布在  Java
关注(0)|答案(1)|浏览(177)

假设我有一个函数

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

我想计算dfs的空间复杂度。调用堆栈的深度将是count。然后在每个调用堆栈上,我需要存储a和b的一个副本。基于这个推理,我倾向于得出这样的结论:空间复杂性是:o((a.length+b.length)*count)。然而,我认为当java将一个对象传递给一个函数时,它只是将a,b地址的一个副本传递给一个给定的函数。因此,我认为每个调用堆栈不需要o(a.length+b.length)空间来保存输入。它只需要空间来存储a和b的地址,这两个地址应该是常量。是这样吗?

sqougxex

sqougxex1#

你最后的陈述是正确的。不复制输入数组,因此所需的唯一额外空间是堆栈深度的线性:o(count)。

相关问题