0

以下は、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²)!)、よくわかりません。

4

1 に答える 1

2

#ソルブ関数は、最悪の場合、グリッド全体に のみが含まれるまで、1 つの要素を次々と に変換します#。しかし、グリッド内の特定のポイントから開始し、次のポイントのみを#直接の隣接ポイントにすることを許可するため、すべての(N²)!可能な順列を取得することはできません。グリッド内のすべてのノードには最大で 8 つの直接隣接があるため、 のようなものしか得られません。境界の要素は隣接要素が少ないため、これを少し改善できます。O(8N2)

最後のfor-loop は、グリッド内のすべての要素を反復し、ソルブ関数を呼び出すため、合計になります。O(N2⋅8N2)

注意:よりもはるかに優れています。8N2(N²)!N² ≥ 20N ≥ 5

注意: 私はd、一定の長さしかないと仮定しました。これが当てはまらない場合はd、複雑さの計算に の長さを追加する必要があります。

于 2015-05-03T04:26:18.407 に答える