0

こんにちは、プログラムの時間と空間の複雑さを見つける必要があります。できれば、実行できる最適化を提案してください。 ................................................................... ................................................................... ................................................................... …………

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;
    }

前もって感謝します

4

1 に答える 1

1

スペースの複雑さを見つけるには、宣言した変数を調べて、単一のプリミティブ変数よりも大きくします。実際、あなたのスペースの複雑さは配列auxilaryとStack stack. 最初のサイズはかなり明確で、2 番目のサイズは完全には理解できませんが、サイズが配列のサイズよりも大きくなることはありません。したがって、空間の複雑さはO(size of(auxilary))またはO(N * M)どこN=as.length()およびM = as[0].length.

ここで、時間の複雑さは少しトリッキーです。アレイ全体で 2 サイクルあるauxilaryため、確実に時間の複雑さは少なくともO( N * M). largestRectangleAreaの行ごとに呼び出す別のサイクルもありますauxilary。この関数のコードを正しく取得した場合、この関数は再び線形であるように見えますが、ここではわかりません。ロジックをよりよく知っているため、おそらくその複雑さをより適切に計算できるようになります。

お役に立てれば。

于 2013-02-08T12:20:29.307 に答える