java - 平铺搜索（嵌套 For 循环）

Question

我正在搜索一个平铺数组，所以基本上有 x 和 y - 例如一个 10 x 10 的网格。目前我在 x 和 y 上使用嵌套 for 循环，但我想知道，因为我对 Java 中的算法设计知之甚少，有没有更快的方法来做到这一点？我转到 (xn,yn) 的每个图块，其中 n 是图块编号，我对其执行操作。

或者这是最快的方法吗？

Answer 1

听起来你正在做这样的事情：

Tile[][] matrix = new Tile[10][10];

//Some code to initialize matrix

for(int x = 0; x < matrix.length; x ++){
    Tile[] row = matrix[x];
    for(int y = 0; y < row.length; x ++){
        Tile cell = row[y];
        //Perform the 'operation' on cell
    }
}

如果是这种情况，那么上面的代码将是 O(n^2) * O('operation')。这是因为访问数组的元素是 O(1)。

如果你有列表而不是数组，那么你应该编写如下代码：

List<List<Tile>> matrix;

//Some code to initialize matrix

for(List<Tile> row : matrix){
    for(Tile cell : row){
        //Perform the 'operation' on cell
    }
}

这隐含地使用了列表提供的迭代器。例如，如果 List 是一个 ArrayList，则迭代器的功能与第一个示例大致相同。如果 List 是 LinkedList，则迭代器将存储对当前正在操作的列表中的节点的引用。对于 LinkedList 和 ArrayList 的花瓶，复杂性仍然存在：O(n^2) * O('operation')

不好的代码是：

LinkedList<LinkedList<Tile>> matrix = new LinkedList<LinkedList<Tile>>();

//Some code to initialize matrix

for(int x = 0; x < matrix.size(); x ++){
    LinkedList<Tile> row = matrix.get(x);
    for(int y = 0; y < row.size(); x ++){
        Tile cell = row.get(y);
        //Perform the 'operation' on cell
    }
}

这个例子是 O(n^4) * O('operation') 因为每次调用 LinkedList.get(x) 都是 O(n) 。记住对数组或 ArrayList 的相同操作是 O(1)。