java - 查找给定 Java 代码的时间和空间复杂度

Question

嗨，我需要找到程序的时间和空间复杂度，请帮助，如果可能请建议可以执行的优化， ..................................................... ..................................................... ..................................................... ...................................................

public class Sol {
    public int findMaxRectangleArea(int [][] as) {
        if(as.length == 0)
       return 0;
    int[][] auxillary = new int[as.length][as[0].length];
        for(int i = 0; i < as.length; ++i) {
            for(int j = 0; j < as[i].length; ++j) {
            auxillary[i][j] = Character.getNumericValue(as[i][j]);
        }
        }
        for(int i = 1; i < auxillary.length; ++i) {
        for(int j = 0; j < auxillary[i].length; ++j) {
            if(auxillary[i][j] == 1)
                    auxillary[i][j] = auxillary[i-1][j] + 1;
            }
        }

    int max = 0;
        for(int i = 0; i < auxillary.length; ++i) {
            max = Math.max(max, largestRectangleArea(auxillary[i]));
        }
        return max;
    }

    private int largestRectangleArea(int[] height) {
        Stack<Integer> stack =
        new Stack<Integer>();
        int max = 0;
        int i = 0;
        while(i < height.length) {
            if(stack.isEmpty() ||
                height[i] >= stack.peek()) {
                stack.push(height[i]);
            i++;
            }
            else {
            int count = 0;
            while(!stack.isEmpty() &&
                stack.peek() > height[i]) {
                    count++;
                    int top = stack.pop();
                max = Math.max(max, top * count);
                }
            for(int j = 0; j < count + 1; ++j) {
                    stack.push(height[i]);
                }
                i++;
            }
        }

        int count = 0;
        while(!stack.isEmpty()) {
            count++;
            max = Math.max(max, stack.pop() * count);
        }
        return max;
    }

提前谢谢你

Answer 1

要找到空间复杂度，请查看您声明的变量，这些变量大于单个原始变量。事实上，我相信您的空间复杂度将由数组 auxilary 和 Stack stack 决定。第一个的大小很清楚，我不完全理解第二个，但我看到它的大小永远不会大于数组中的一个。所以我会说空间复杂度是 O(size of(auxilary)) 或 O(N * M) 其中 N=as.length() 和 M = as[0].length。

现在时间复杂度有点棘手。整个 auxilary 数组有两个循环，因此时间复杂度至少为 O( N * M)。您还有另一个循环，它为 auxilary 的每一行调用 largestRectangleArea。如果我正确地得到了这个函数中的代码，那么这个函数似乎又是线性的，但我在这里不确定。由于您更了解逻辑，因此您可能能够更好地计算其复杂性。

希望这对您有所帮助。