Complessità del tempo di ricerca di un bacino

Question

Il seguente algoritmo viene utilizzato per trovare un bacino nella matrice. L'intera domanda è la seguente:

La matrice 2-D viene indicata dove ogni cella rappresenta l'altezza della cella. L'acqua può scorrere dalla cella con altezza maggiore a quella inferiore. Un bacino è quando non c'è una cella con altezza inferiore nei vicini (sinistra, destra, su, giù, diagonale). Devi trovare blocco dimensione massima blocco.

Ho implementato il codice. Sto cercando timeComplexity. Secondo me la complessità temporale è O (n * m) dove n e m è la riga e la colonna della matrice. Si prega di verificare.

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

Sì, il codice (ammesso che funziona, non ho provato) è O (n * m) nel tempo, e O (n * m) nello spazio.

Le complessità non possono essere inferiori a O (n * m), poiché ogni cella può essere una parte di un bacino massimo adiacente nel caso generale, e tutti devono quindi essere (in generale) esaminati. La complessità è O (n * m) a causa dei due cicli for nidificati in getMaxBasin, e il fatto che visitato [i] [j] può essere impostato solo in un singolo punto (all'interno di scan()) e proibisce le visite successive della stessa cella.

A causa della ricorsione, ogni volta che si concatena una scansione di chiamata(), si aggiunge allo stack. Con una catena sufficientemente lunga di scansioni(), è possibile imbattersi in limiti di stack. Lo scenario peggiore è uno schema a zig-zag in modo che lo stack finisca per contenere una chiamata scan() per ogni cella.