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

该算法的大运行时间是什么？我相信这是O((N²)!)，但我不确定。

Answer 1

求解函数在另一个元素变成 #，在最坏的情况下，直到整个网格仅包含 #。但是，由于您从网格中的特定点开始，并且仅允许下一个#成为直接邻居，因此您不会获得所有(N²)!可能的排列。您只会得到诸如O(8N2)之类的东西，因为网格中的每个节点最多都有8个直接邻居。边界的元素的邻居较少，因此您可以改进一点。

for -loop在末端，迭代在网格中的所有元素上，并调用求解功能，因此总共是O(N2⋅8N2)。

注意：8N2比(N²)!好得多，即N² ≥ 20，即N ≥ 5。

注意：我以为d只有一个恒定的长度。如果这不是真的，则必须将d的长度添加到复杂度计算中。