java - 寻找盆地的时间复杂度

Question

以下算法用于在矩阵中查找盆地。整题如下:

2-D matrix is given where each cell represents height of cell. Water can flow from cell with higher height to lower one. A basin is when there is no cell with lower height in the neighbours (left,right,up,down,diagonal). You have to find maximum size basin block.

我已经实现了代码。我正在寻找时间复杂度。在我看来，时间复杂度是 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(n * m)，在空间上是 O(n * m)。

复杂度不能低于 O(n * m)，因为在一般情况下任何单元格都可以是相邻最大盆地的一部分，因此必须(通常)检查所有单元格。由于 getMaxBasin 中的两个嵌套 for 循环，以及 visited[i][j] 只能设置在一个地方(在 scan() 内)并禁止以后访问的事实，您的复杂度为 O(n * m)同一个单元格。

由于递归，每次链接调用 scan() 时，都会将其添加到堆栈中。使用足够长的 scan() 调用链，您可能会遇到堆栈限制。最坏的情况是锯齿形模式，因此堆栈最终包含对每个单元格的 scan() 调用。