Сложность нахождения бассейна

Question

Для нахождения бассейна в матрице используется следующий алгоритм. Весь вопрос заключается в следующем:

2-D матрица задается там, где каждая ячейка представляет собой высоту ячейки. Вода может вытекать из ячейки с более высокой высотой в нижнюю. В бассейне есть , у соседей нет ячейки с меньшей высотой (влево, вправо, вверх, вниз, по диагонали). Вы должны найти максимальный размер бассейна блок.

Я внедрил код. Я ищу времяComplexity. На мой взгляд, сложность времени - это O (n * m), где n и m - строка и столбец матрицы. Пожалуйста, подтвердите.

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

Да, ваш код (если он работает, я не проверял) является O (Н * м) во время и O (Н * м) в пространстве.

Сложности не могут быть ниже O (n * m), поскольку любая ячейка может быть частью соседнего макс-бассейна в общем случае, и поэтому все должны быть (в общем) рассмотрены. Ваша сложность - O (n * m) из-за двух вложенных for-loops в getMaxBasin, а тот факт, что посетил [i] [j], можно установить только в одном месте (внутри scan()) и запрещает более поздние посещения той же ячейки.

Из-за рекурсии каждый раз, когда вы связываете вызов(), вы добавляете в стек. При достаточно длинной цепочке вызовов scan() вы можете столкнуться с ограничениями стека. В худшем случае это шаблон зигзага, так что стек заканчивается с вызовом scan() для каждой ячейки.