问题描述
我正在准备一些编码采访，并提出了以下问题的解决方案:
I am preparing for some coding interviews and came up with a solution to the following problem:
在单词列表中查找可以由其他单词组成的最长单词".
"Find longest word that can be made of other words in a list of words".
我很难弄清楚算法的时间复杂度.如果您能帮助我弄清楚以下代码的时间复杂度，那将是很好的.
I have a hard time figuring out the time complexity of my algorithm. It would be great, if you can help me to figure out the time complexity of the following code.
它大于n²(用于排序的n⋅log n，number_of_words ⋅ word_length + recursion)，但由于递归部分，不确定如何计算确切的复杂度.
It is more than n² (n⋅log n for sorting, number_of_words ⋅ word_length + recursion), but not sure how to calculate the exact complexity due to recursion part.
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
推荐答案
让n为列表中的单词数，而m为最长单词的长度.
Let n be the number of words in the list and m the length of the longest word.
for循环遍历words，直到valid_word返回true.最坏的情况是，列表中的其他单词都无法与其他单词连接在一起.因此，这给了您一个系数n.
The for-loop iterates over the words until valid_word returns true. The worst case would be, that non of the words can be concatenated from other words in the list. So this gives you a factor n.
valid_word遍历单词中的所有字符并调用valid_pair，其复杂度为O(f)，其中f = f(n,m)是in运算符的复杂度. (我不知道它是如何实现的).如果对于每个字符left在words中，但right不在valid_word中，则valid_word被递归调用m次，得出以下公式:
valid_word iterates over all characters in a word and calls valid_pair which has the complexity O(f), where f = f(n,m) is the complexity of the in operator. (I don't know, how it is implemented). If for every character left is in words, but right is not, valid_word is called recursively m times, resulting in this formula:
T(m) = f + Σ T(m-i) < f + (m-1) ⋅ T(m-1) < m!⋅f
所以valid_word在O(m!⋅f(n,m))中(可以改进).
So valid_word is in O(m!⋅f(n,m)) (this can be improved).
总体复杂度为O(n⋅m!⋅f(n,m) + n⋅log(n)).这是一个上限，因此也许可以通过显示不可能有一个强制算法执行所有步骤的输入来改善这一点.
The over all complexity is O(n⋅m!⋅f(n,m) + n⋅log(n)). This is an upper bound, so maybe you can improve this, by showing that it is not possible to have an input that forces the algorithm to do all the steps.
但是请考虑这样的输入(带空格仅是为了提高可读性)
But think of an input like this (withe spaces are only for better readability)
words = ['ab ac ad ae','ab ac ad af', ... , 'ab ac ad az',
'ab ac ad', 'ab ac', 'ab']
这些单词中没有一个可以与其他单词串联，但是算法必须尝试许多组合.这个例子可以改进和扩展.
Non of these words can be concatenated from the others, but the algorithm has to try many combinations. This examples can be improved and extended.
这篇关于python代码的时间复杂度，用于查找可以由列表中其他单词组成的最长单词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！