关于双数组移除元素算法的Big O表示法时间复杂度疑问

你这个观察特别精准！很多人一看到两层嵌套循环就直接套O(n²)，但忽略了元素被移除后后续迭代次数会减少这个关键细节——这其实是对Big O表示法理解的一个常见误区。

咱们结合你的场景具体拆解：假设arraylist1有n个元素，arraylist2初始有m个元素，核心逻辑是外层遍历arraylist1的每个元素，内层遍历arraylist2的当前元素，满足条件就移除该元素。

1. 最坏情况：仍可能是O(n²) #

如果遍历下来arraylist2里的元素一个都没被移除（比如条件从未满足），那外层循环会跑满n次，每次内层都完整遍历m个元素，总操作次数就是n*m。如果n和m的规模接近（比如两个列表长度差不多），那这时候时间复杂度就是O(n²)——这就是传统嵌套循环的最坏情况复杂度。

2. 实际/平均情况：复杂度会低于O(n²) #

但正如你注意到的，一旦元素被移除，后续的内层循环就不会再遍历到它了，这会大幅减少总操作次数。这里可以分两种子情况看：

• 如果大部分元素被移除：比如arraylist2里的元素几乎都能匹配到arraylist1的元素并被移除，那每个被移除的元素只会被检查1次，未被移除的元素才会被多次检查。极端情况是所有元素都被移除，总操作次数就是m（内层遍历的总次数）加上n（外层循环次数），复杂度降到O(n + m)。
• 如果部分元素被移除：总操作次数会介于O(n+m)和O(n*m)之间，具体取决于被移除元素的数量——移除的元素越多，实际执行的操作就越少，复杂度越接近线性。

小优化建议 #

如果想让这个逻辑的时间复杂度更稳定（不管匹配情况如何都保持线性），可以先把arraylist2的元素存入哈希集合（查找时间O(1)），然后遍历arraylist1，找到匹配元素就从集合中移除，最后再把集合转回列表。这样总复杂度固定为O(n + m)，比依赖移除元素减少遍历次数的逻辑更高效可控。

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