递归函数的空间复杂度估计

Question

我正在学习算法和数据结构，现在我正在考虑时间和空间的复杂性。

我必须解决一个问题，他们告诉（根据我的代码）时间和空间的复杂性。

这是代码：

public class B { 

    public static int minSum = -1; 

    public static void main(String[] args) { 
     int objects, sumA = 0, sumB = 0; 

     Scanner readInput = new Scanner(System.in); 

     objects = readInput.nextInt(); 

     int[] trunk = new int[objects]; 

     if (objects == 0) { 
      System.out.print(0 + "\n"); 
     } else if (objects == 1) { 
      trunk[0] = readInput.nextInt(); 
      System.out.print(trunk[0] + "\n"); 
     } else { 
      for (int i = 0; i < objects; i++) { 
       trunk[i] = readInput.nextInt(); 
      } 

      bruteforce(trunk, sumA, sumB, 0); 

      System.out.println(minSum); 
     } 
    } 

    public static void bruteforce(int[] trunk, int sumA, int sumB, int index) { 
     int partialDiff; 

     if (minSum == 0) { 
      System.out.println(minSum); 
      System.exit(0); 
     } else if (index == trunk.length) { 
      partialDiff = Math.abs(sumA - sumB); 
      if (partialDiff < minSum || minSum == -1) { 
       minSum = partialDiff; 
      } 
     } else { 
      bruteforce(trunk, sumA + trunk[index], sumB, index + 1); 
      bruteforce(trunk, sumA, sumB + trunk[index], index + 1); 
     } 
    } 
} 

基本上用户首先输入号码的对象，然后输入的，对于每个对象，它的值。该算法将通过两个袋子来分配物体，并且必须计算当通过两个袋子分配物体时可以计算的最小差异。

我相信它需要指数时间，但我正在为空间复杂性进行估计。你能指出我在某个方向吗？

Answer 1

空间复杂度是线性的 - O(n)。

您可以通过将每个函数调用中使用的内存量乘以最大递归深度来计算此值。

在每个函数调用中都会使用恒定数量的内存 - 只有partialDiff和堆栈信息。

要确定最大递归深度，基本上只需看index（因为这是决定何时停止递归更深的变量）。

• 你打电话与index = 0
• 函数在每个递归调用，index增加一。
• 只要index达到数组的大小，它就会停止。

注意函数调用深度优先，意味着第二个电话前，将全面评估，以bruteforce第一个呼叫，因此只有一个会占用内存在的时间。

因此，对于长度为2的数组，它是这样的：（Call 1是第一个函数调用，Call 2第二）

Call with index 0 
    Call 1 with index 1 
    Call 1 with index 2 
    Call 2 with index 2 
    Call 2 with index 1 
    Call 1 with index 2 
    Call 2 with index 2 

所以最大深度（因而空间复杂度）为3 ，比数组中的项目数量多一个。

因此它是memory used in each function call * max depth = constant * linear = linear。