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

kx5bkwkv 于 2021-07-06 发布在 Java

关注(0)|答案(1)|浏览(248)

假设我有一个函数

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的地址，这两个地址应该是常量。是这样吗？

Java Algorithm space-complexity time-complexity

来源：https://stackoverflow.com/questions/65015196/how-to-count-the-space-used-to-hold-the-input-on-the-call-stack-for-recursion