Zaman havza bulmanın karmaşıklığı

Question

Aşağıdaki algoritma, matriste bir havza bulmak için kullanılır. Bütün soru şu şekildedir: Her bir hücrenin, hücre yüksekliğini temsil ettiği 2-D matrisi verilmiştir. Su , daha yüksek bir yüksekliğe sahip olan hücreden aşağı doğru akabilir. Bir havza ne zaman komşuları (sol, sağ, yukarı, aşağı, diyagonal) alt yüksekliği olan bir hücre yok. Maksimum boyutta havza bloğunu bulmanız gerekiyor. Kodu uyguladık. TimeComplexity için arıyorum. Benim düşünceme göre zaman karmaşıklığı O (n * m), burada n ve m matrisin satır ve sütunu. Lütfen tanımla. zamanında O (n * m) olup, O (n * m) uzayda;

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

Evet, kodu (bunu test etmedim çalıştığını varsayarak). Herhangi bir hücre genel durumdaki komşu bir havzada bir parça olabileceğinden ve bu nedenle de hepsinin (genel olarak) incelenmesi gerektiği için, kompleksler O (n * m) 'den daha düşük olamazlar. GetMaxBasin'de iç içe geçmiş iki döngüsünden dolayı karmaşıklığınız O (n * m) şeklindedir ve [i] [j] 'yi ziyaret etmesi gerçeği yalnızca tek bir yerde (scan()) ayarlanabilir ve daha sonra ziyaretleri yasaklar. aynı hücrenin.

Özyineleme nedeniyle, bir arama taramasını() her zincirlediğinizde, yığına ekliyorsunuz demektir. Yeterince uzun bir tarama() zinciri çağrısı ile yığın sınırlarına erişebilirsiniz. En kötü durum senaryosu, her bir hücrenin her biri için bir tarama() çağrısı içeren yığının bittiği bir zikzak desenidir.