建议的解决方案的时间复杂度是多少？

Question

这是解决以下问题的方法:给定长度为N的两个字符串s和t，在s和t内交换两个字符后，在字符串s和t中找到最大可能的匹配对。交换是交换si和sj，其中si和sj分别表示s的ith和jth索引处存在的字符。这两个字符串的匹配对被定义为si和ti相等的索引数。注意:这意味着您必须在不同的索引上交换两个字符。

这其中的时间复杂性是多少？

s = "abcd"
t = "adcb"

tl = list(t)
pairs = []

for i in range(len(list(s))):
    window = 1
    j = i + window 
    
    while j < len(s):
        sl = list(s)
        sl[i], sl[j] = sl[j], sl[i]

        ds = {sl[k]: k for k in range(len(sl))}
        dt = {tl[k]: k for k in range(len(tl))}
        
        pairs.append(len(ds.items() & dt.items()))
        j += 1
        
max(pairs)

Answer 1

算法的复杂性是O(N立方)。

嵌套循环在数组中的最大深度为3。在这种情况下，我们可以忽略depth内部的一系列循环来计算复杂性。(复杂度为O(N_N_3N)，相当于O(N)立方)

对于如何计算复杂性here，有一个很好的解释。