遞歸函數的空間複雜度估計

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。