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

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 都会增加 1。
• 一旦 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，比数组中的项目数多 1。

所以它是每个函数调用中使用的内存 * max depth = constant * linear = linear。