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

Question

这是以下问题的解决方案：给定两个长度为 N 的字符串 s 和 t，在恰好交换 s 中的两个字符后，找到字符串 s 和 t 中可能匹配对的最大数目。交换是交换 s[i] 和 s[j]，其中 s[i] 和 s[j] 分别表示出现在 s 的第 i 个和第 j 个索引处的字符。两个字符串的匹配对定义为 s[i] 和 t[i] 相等的索引数。注意：这意味着您必须交换不同索引处的两个字符。

这个的时间复杂度是多少？

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。在这种情况下，我们可以忽略 while 内的一系列循环来计算复杂度。（复杂度为 O(NN3N) 等同于 O(N³))

关于如何计算复杂度有很好的解释here

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

What is the time complexity of suggested solution?

python

time-complexity