Временная сложность решателя Boggle

Question

Вот (уродливый) алгоритм поиска всех слов в Boggle:

d = {'cat', 'dog', 'bird'}

grid = [
    ['a', 'd', 'c', 'd'],
    ['o', 'c', 'a', 't'],
    ['a', 'g', 'c', 'd'],
    ['a', 'b', 'c', 'd']
]

found = {}

N = 4

def solve(row, col, prefix):
    if prefix in d and prefix not in found:
        found[prefix] = True
        print prefix

    for i in xrange(max(0, row - 1), min(N, row + 2)):
        for j in xrange(max(0, col - 1), min(N, col + 2)):
            c = grid[i][j]
            if c != '#' and not (row == i and col == j):
                grid[i][j] = '#'
                solve(i, j, prefix + c)
                grid[i][j] = c


for row in xrange(N):
    for col in xrange(N):
        c = grid[row][col]
        grid[row][col] = '#'
        solve(row, col, c)
        grid[row][col] = c

Каково время выполнения Big-O этого алгоритма? Я верю что O((N²)!), но я не уверен.

Answer 1

Функция решения превращает один элемент за другим в #в худшем случае, пока вся сетка не содержит только #, Но так как вы начинаете с определенной точки в сетке и разрешаете только следующее # быть прямым соседом, вы не получите все (N²)! возможные перестановки. Вы получаете только что-то вроде O(8N2)потому что каждый узел в вашей сетке имеет не более 8 прямых соседей. Элементы на границах имеют меньше соседей, так что вы можете немного улучшить это.

for-loop в конце, перебирает все элементы в сетке и вызывает функцию решения, так что это будет O(N2⋅8N2) в целом.

Обратите внимание: 8N2 намного лучше чем (N²)! пока N² ≥ 20т.е. N ≥ 5,

Обратите внимание: я предположил, что d имеет только постоянную длину. Если это не так, вы должны добавить длину d к сложности расчетов.