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循环，遍历网格中的所有元素并调用求解函数，所以它会是O(N2⋅8N2)一共

注意：8N2比(N²)!好很多只要 N² ≥ 20，即 N ≥ 5.

注意：我假设 d 只有一个固定长度。如果不是这样，则必须将 d 的长度添加到复杂性计算中。

Boggle求解器的时间复杂度

Time complexity of Boggle solver

python

algorithm

big-o

time-complexity

boggle