查找給定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。如果我正確地得到這個函數的代碼，看起來這個函數再次是線性的，但我不確定這裏。既然你更瞭解這個邏輯，你可能會更好地計算它的複雜性。

希望這會有所幫助。