搜索问题的时间复杂度分析

Question

有人向我介绍了一个面试问题示例，给定一个二维字符数组和一个单词，在数组中找到单词，其中单词的下一个字符位于前一个字符的右侧或下方， return 找到的每个字符的坐标列表。

我写了下面的代码来解决这个问题：

co_ords = []

def init_recursion(word, grid):
    co_ords.clear()
    return find_word(word, grid, 0, 0, True, 0)

def find_word(word, grid, x, y, explore, pos):
    word_len = len(word) - pos
    if word_len == 0:
        return True

    x_size = len(grid[0])
    y_size = len(grid)

    if word_len > (x_size - x) + (y_size - y):
        return False

    try:
        char_on = grid[y][x]

        if word[pos] == char_on:
            co_ords.append((y, x))
            if find_word(word, grid, x + 1, y, False, pos + 1):
                return True
            elif find_word(word, grid, x, y + 1, False, pos + 1):
                return True
            else:
                co_ords.pop()
        if word_len - 1 > (x_size - x) + (y_size - y):
            return False
        if explore and find_word(word, grid, x + 1, y, True, 0):
            return True
        else:
            return explore and find_word(word, grid, x, y + 1, True, 0)
    except IndexError:
        return False

# Valid grid and word combinations:
grid1 = [
    ['c', 'c', 'x', 't', 'i', 'b'],
    ['c', 'c', 'a', 't', 'n', 'i'],
    ['a', 'c', 'n', 'n', 't', 't'],
    ['t', 'c', 's', 'i', 'p', 't'],
    ['a', 'o', 'o', 'o', 'a', 'o'],
    ['o', 'a', 'a', 'a', 'o', 'o'],
    ['k', 'a', 'i', 'c', 'k', 'i']
]
word1 = 'catnip' >>> [(1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4)]
word2 = 'cccc' >>> [(0, 0), (0, 1), (1, 1), (2, 1)] (one choice of many)
word3 = 's' >>> [(3, 2)]
word4 = 'bit' >>> [(0, 5), (1, 5), (2, 5)]

我对此的复杂度分析如下：
其中：

R = 行数
C = 列数
W = 单词中的字符

find_word函数将循环遍历整个二维网格RC - W²次，并且对于每个探索调用, 最多可以回避 Wlog(W) 次尝试找到匹配项。因此，在最坏的情况下，总共会有 Wlog(W)(RC - W²) 次递归调用。

因此我的问题是：

一、我上面的复杂度分析是否正确？
二，在大O表示法中（最坏情况时间复杂度），这将如何表示？
我认为它可能是以下之一：
1. O(RCW(log(W)) - W³)
2. O(RCW(log(W)))
  但我不确定哪个 - 通常较小的术语会在大 O 中被忽略，但是我不确定，因为 W 出现在 n^{3 中} 和 n³log(n) 项。

Answer 1

我不同意你的搜索深度是 O(Wlog(W))。在最坏的情况下，每个中间字母（最后一个字母除外）都与单词匹配，您的递归将具有 2 的分支因子，并将探索 2^W 路径。举个例子，一个非常大的网格，里面全是A，右下角只有一个B，还有一个搜索词AAA...AB。您可以看到这将如何呈指数级增长（相对于 W）。

你也是对的，因为你会忽略较小的项，所以总的来说我认为时间复杂度应该是 O(RC*2^W)。

搜索问题的时间复杂度分析

Time complexity analysis of search problem

python

performance

time-complexity