python 代码的时间复杂度，用于查找可以由列表中的其他单词组成的最长单词

Question

我正在准备一些编码面试，并提出了解决以下问题的方法：

"Find longest word that can be made of other words in a list of words".

我很难弄清楚我的算法的时间复杂度。如果您能帮助我计算出以下代码的时间复杂度，那就太好了。

超过n²（n⋅log n用于排序，number_of_words ⋅ word_length + recursion），但由于递归部分不确定如何计算确切的复杂度。

def valid_pair(a,b, words):
    return  a in words and b in words

def valid_word(word, words):
    for i in range(len(word)):
        left, right = word[:i], word[i:]
        valid =  valid_pair(left, right, words)
        if valid:
            return valid
        elif left in words:
            return valid_word(right, words)

    return False


words = ["cde","abcde","bcd","c","d","e","a"]

words = sorted(words, key = len, reverse = True)
for w in words:
    if valid_word(w, words):
        print w
        break

Answer 1

设 n 为列表中的单词数，m 为最长单词的长度。

for 循环遍历 words 直到 valid_word returns true。最坏的情况是，没有一个词可以从列表中的其他词连接起来。所以这给了你一个因素 n.

valid_word 遍历单词中的所有字符并调用复杂度为 O(f) 的 valid_pair，其中 f = f(n,m) 是 in 的复杂度操作员。（我不知道，它是如何实现的）。如果对于每个字符 left 在 words 中，但 right 不在，则 valid_word 被递归调用 m 次，导致此公式：

T(m) = f + Σ_i=1,...m-1 T(m-i) < f + (m-1) ⋅ T(m-1) < m!⋅f

所以valid_word在O(m!⋅f(n,m))（这个可以改进）。

总体复杂度为 O(n⋅m!⋅f(n,m) + n⋅log(n))。这是一个上限，所以也许你可以改进这一点，通过证明不可能有一个输入来强制算法完成所有步骤。

但是想想这样的输入（空格只是为了更好的可读性）

words = ['ab ac ad ae','ab ac ad af', ... , 'ab ac ad az',
         'ab ac ad', 'ab ac', 'ab']

这些词中没有一个可以与其他词串联，但算法必须尝试多种组合。这个例子可以改进和扩展。

python 代码的时间复杂度，用于查找可以由列表中的其他单词组成的最长单词

Time complexity of python code for finding the longest word that can be made of other words in the list

python

performance

big-o

time-complexity