時間驚奇的複雜求解

Question

這裏是查找所有單詞驚奇一（醜）算法：

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運行？我相信這是O((N²)!)，但我不確定。

Answer 1

solve函數將一個元素對另一個元素轉換爲#，最糟糕的情況是直到整個網格僅包含#。但是，由於您從網格中的特定點開始，只允許下一個#成爲直接鄰居，因此您不會獲得所有(N²)!可能的排列。你只能得到類似O(8N2)的東西，因爲網格中的每個節點最多有8個直接鄰居。在邊界的元素有較少的鄰居，所以你可以改善這一點。

for -loop在最後遍歷網格中的所有元素並調用solve函數，因此它總共爲O(N2⋅8N2)。

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

注意：我認爲，那d只有一個恆定的長度。如果不是這樣，則必須將d的長度添加到複雜度計算中。