сложность обхода массива грубой силы

Question

Если у меня есть сетка 4x4, например, и я хочу начать с произвольной ячейки (i, j), а затем хочу пройти по каждому пути, не переходя на себя, какова сложность (большой o) этого?Я написал следующий код:

traverse(int[][]grid, int i, int j, boolean[][] visited){
    for(int x = -1; x<=1; x++){
       for(int y=-1; y<=1; y++){
           if(inBounds(grid, i+x, j+y), !visited[i+x][j+y]){
              traverse(grid, i+x, j+y, copyOfAndSet(visited, i+x, j+y));
           }
       }
    }
}

Предположим, что inBounds существует, а copyOfAndSet существует и равен O (1) (не O (n * n)), поскольку я реализовал это с побитовыми операциями, но для ясности использовалмассив логических значений здесь.

Каково время выполнения алгоритма выше в сетке NxN.

Спасибо

Answer 1

Во-первых, ваш алгоритм может проходить по диагонали, я не уверен, что это то, что вы хотели ... во-вторых: сначала он должен посетить начальный узел (выполнить copyOfAndSet), но ваш алгоритм сначала перемещается в направлении (-1 , -1).

При обходе массива алгоритм посещает каждый узел и в каждом узле он проверяет 9 соседей (он должен проверить 8 BTW, (0, 0) не имеет смысла). Для сетки NxN это 9 * N * N или просто O(N^2) Если copyOfAndSet действительно копирует массив, тогда это N * N для каждой ячейки, поэтому O(N^4).

Answer 2

Если Я понимаю ваш вопрос, вы хотите перечислить все самостоятельных обходов на двумерной сетке. (Вы сказали «путешествовать по каждому пути, не переходя на себя»)

Вы можете найти несколько статей по этому поводу, погуглив по этим ключевым словам.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.5913

Проблема, кажется, # P-полная, согласно статье.