Độ phức tạp của thời gian tìm kiếm một lưu vực

Question

Thuật toán sau đây được sử dụng để tìm một lưu vực trong ma trận. Toàn bộ câu hỏi như sau:

Ma trận 2-D được cung cấp cho mỗi ô đại diện cho chiều cao của ô. Nước có thể chảy từ ô có chiều cao cao hơn xuống thấp hơn. Lưu vực là khi không có ô nào có chiều cao thấp hơn ở hàng xóm (trái, phải, lên, xuống, chéo). Bạn phải tìm kích thước tối đa lưu vực khối.

Tôi đã triển khai mã. Tôi đang tìm timeComplexity. Theo quan điểm của tôi, độ phức tạp là O (n * m) trong đó n và m là hàng và cột của ma trận. Xin vui lòng xác minh.

public final class Basin { 

    private Basin() {} 

    private static enum Direction { 
     NW(-1, -1), N(0, -1), NE(-1, 1), E(0, 1), SE(1, 1), S(1, 0), SW(1, -1), W(-1, 0); 

     private int rowDelta; 
     private int colDelta; 

     Direction(int rowDelta, int colDelta) { 
      this.rowDelta = rowDelta; 
      this.colDelta = colDelta; 
     } 

     public int getRowDelta() { 
      return rowDelta; 
     } 

     public int getColDelta() { 
      return colDelta; 
     } 
    } 

    private static class BasinCount { 
     private int count; 
     private boolean isBasin; 
     private int item; 

     BasinCount(int count, boolean basin, int item) { 
      this.count = count; 
      this.isBasin = basin; 
      this.item = item; 
     } 
    }; 

    /** 
    * Returns the minimum basin. 
    * If more than a single minimum basin exists then returns any arbitrary basin. 
    * 
    * @param m  : the input matrix 
    * @return  : returns the basin item and its size. 
    */ 
    public static BasinData getMaxBasin(int[][] m) { 
     if (m.length == 0) { throw new IllegalArgumentException("The matrix should contain atleast one element."); } 

     final boolean[][] visited = new boolean[m.length][m[0].length]; 
     final List<BasinCount> basinCountList = new ArrayList<>(); 

     for (int i = 0; i < m.length; i++) { 
      for (int j = 0; j < m[0].length; j++) { 
       if (!visited[i][j]) { 
        basinCountList.add(scan(m, visited, i, j, m[i][j], new BasinCount(0, true, m[i][j]))); 
       } 
      } 
     } 

     return getMaxBasin(basinCountList); 
    } 


    private static BasinData getMaxBasin(List<BasinCount> basinCountList) { 
     int maxCount = Integer.MIN_VALUE; 
     int item = 0; 
     for (BasinCount c : basinCountList) { 
      if (c.isBasin) { 
       if (c.count > maxCount) { 
        maxCount = c.count; 
        item = c.item; 
       } 
      } 
     } 
     return new BasinData(item, maxCount); 
    } 



    private static BasinCount scan(int[][] m, boolean[][] visited, int row, int col, int item, BasinCount baseCount) { 

     // array out of index 
     if (row < 0 || row == m.length || col < 0 || col == m[0].length) return baseCount; 

     // neighbor "m[row][col]" is lesser than me. now i cannot be the basin. 
     if (m[row][col] < item) { 
      baseCount.isBasin = false; 
      return baseCount; 
     } 

     // my neighbor "m[row][col]" is greater than me, thus not to add it to the basin. 
     if (m[row][col] > item) return baseCount; 

     // my neighbor is equal to me, but i happen to have visited him already. thus simply return without adding count. 
     // this is optimisitic recursion as described by rolf. 
     if (visited[row][col]) { 
      return baseCount; 
     } 

     visited[row][col] = true; 
     baseCount.count++; 

     for (Direction dir : Direction.values()) { 
      scan(m, visited, row + dir.getRowDelta(), col + dir.getColDelta(), item, baseCount); 
      /** 
      * once we know that current 'item' is not the basin, we do "want" to explore other dimensions. 
      * With the commented out code - consider: m3 
      * If the first 1 to be picked up is "1 @ row2, col4." This hits zero, marks basin false and returns. 
      * Next time it starts with "1 @ row 0, col 0". This never encounters zero, because "1 @ row2, col4." is visited. 
      * this gives a false answer. 
      */ 
//   if (!baseCount.basin) { 
//    System.out.println(baseCount.item + "-:-:-"); 
//    return baseCount; 
//   } 
     } 

     return baseCount; 
    } 

Answer 1

Có, mã của bạn (giả sử nó hoạt động; tôi chưa thử) là O (n * m) đúng lúc và O (n * m) trong không gian.

Độ phức tạp không thể thấp hơn O (n * m), vì bất kỳ ô nào cũng có thể là một phần của lưu vực tối đa lân cận trong trường hợp chung và tất cả phải được kiểm tra. Độ phức tạp của bạn là O (n * m) do hai vòng lặp lồng nhau trong getMaxBasin và thực tế truy cập [i] [j] chỉ có thể được đặt ở một nơi duy nhất (bên trong quét()) và cấm truy cập sau này của cùng một ô.

Do đệ quy, mỗi khi bạn chuỗi cuộc gọi quét(), bạn sẽ thêm vào ngăn xếp. Với chuỗi cuộc gọi quét() đủ dài, bạn có thể chạy vào giới hạn ngăn xếp. Kịch bản trường hợp xấu nhất là một mẫu zig-zag để ngăn xếp kết thúc có chứa một cuộc gọi scan() cho mỗi một ô.