查找给定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和Stackstack。第一个的大小非常清晰，我不完全理解第二个，但是我发现它的大小永远不会比数组大。所以我想说的空间复杂性是O(size of(auxilary))或O(N * M)其中N=as.length()和M = as[0].length。

现在时间复杂度有点棘手。您在整个auxilary阵列上有两个周期，因此确保时间复杂度至少为O(N * M)。您还有另一个周期，调用largestRectangleArea为每行auxilary。如果我正确地得到这个函数的代码，看起来这个函数再次是线性的，但我不确定这里。既然你更了解这个逻辑，你可能会更好地计算它的复杂性。

希望这会有所帮助。