Поиск плитки (вложенные для циклов)

Question

Я искал массив черепицы, поэтому в основном есть x и y - скажем, например, сетка 10 на 10. В настоящее время я использую вложенный цикл for over x и y, но мне интересно, так как я мало знаю об алгоритмическом дизайне в 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 ('Операция'). Это следует из того, что доступ к элементам массива равен 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 ('Операция')

Кода, который будет плох:

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 ('операция'), потому что каждый вызов LinkedList.get (x) является O (n). Повторите ту же операцию в массиве, или ArrayList - O (1).