求equal方法的时间复杂度：两次调用thing函数的情况分析

1. 先拆解thing函数的时间复杂度 #

thing函数内有一个遍历整个输入列表的for循环，循环次数完全等于输入列表的长度，参数pos在函数中没有被使用（属于冗余参数）。假设输入列表的长度为k，那么thing的时间复杂度为 O(k)。

2. 分析equal函数的总时间复杂度 #

• 外层有一个for循环，循环次数等于列表l的长度，记为n。
• 每次循环中会调用两次thing：
  • 调用thing(l, i)时，输入列表是l，长度为n，所以这部分的时间复杂度是O(n)；
  • 调用thing(l2, i)时，输入列表是l2，长度记为m，这部分的时间复杂度是O(m)。
• 单次循环的总时间为O(n + m)，外层循环执行n次，因此equal的总时间复杂度为 O(n(n + m))*。

如果l和l2长度相同（即n=m），时间复杂度可简化为 O(n²)。

结合测试用例的验证 #

你给出的测试用例中，l1长度为5，l2长度为4：

• equal的外层循环执行5次；
• 每次循环内，thing(l1, i)遍历5个元素，thing(l2, i)遍历4个元素，单次循环共9次操作；
• 总操作次数为5*9=45，完全符合上述复杂度推导的结果。

内容的提问来源于stack exchange，提问作者simulated_mand