我的算法的时空复杂度

Question

我想知道我的算法的时间和空间复杂度是多少。输入是一个歌曲列表，输出是歌曲的最长列表，其中一首歌的最后一个单词与下一首歌的第一个单词相同。例如，如果输入是

test_list = ["Every Breath You Take", "Down By the River", "River of Dreams", "Take me to the River", "Dreams",
"Blues Hand Me Down", "Forever Young", "American Dreams", "All My Love", "Cantaloop", "Take it All",
"Love is Forever", "Young American"]

输出将是

['Every Breath You Take', 'Take it All', 'All My Love', 'Love is Forever', 'Forever Young', 'Young American', 'American Dreams', 'Dreams']

需要注意的是，如果有两个长度相等的链，那么我将返回按字母顺序排列的链

我的代码

def song_chain(song_list):
def chain(start, song_list):
remaining = list(song_list)
del remaining[remaining.index(start)]
possibles = [x for x in remaining if x.split()[0] == start.split()[-1]]
max_chain = []

for c in possibles:
l = chain(c, remaining)
if len(l) > len(max_chain):
max_chain = l
if len(l) == len(max_chain):
for i in range(len(l)):
selected = None
if l[i] != max_chain[i]:
selected = min(l[i], max_chain[i])
if selected == l[i]:
max_chain = l
return [start] + max_chain

return chain(song_list[0], song_list)

Answer 1

在每一步中，您调用最多n递归调用(当所有歌曲都可能时)，并且对于每个调用，您的算法需要O(n^2)来处理(双循环)，因此我们得到以下关系:

T(n) <= n * T(n - 1) + O(n^2)
= n * (n - 1) * T(n - 2) + O(n^2) 
....
= n! T(0) + a O(n^2)

时间复杂度为O(n!)。

对于空间来说，考虑递归树总是有帮助的，在最坏的情况下，深度为n，当总是有一个匹配时，在每个深度我们存储一个大小为n-d的列表(d是深度)，所以空间是O(n^2)。