C#中拼接两个HashSet的时间复杂度是多少？

首先得明确：你用的Concat是LINQ的扩展方法，它不会修改原有的两个HashSet，也不会立刻生成新的集合——它返回的是一个IEnumerable<T>类型的延迟序列。也就是说，调用firstSet.Concat(secondSet)这行代码本身几乎不消耗时间，复杂度是O(1)，因为只是创建了一个负责后续遍历的枚举器对象，没有碰任何集合里的元素。

但真正的时间消耗在你实际遍历这个拼接后的序列的时候：比如你把它转成新的HashSet、List，或者用foreach循环迭代的时候，需要完整遍历第一个集合的所有元素（假设元素数为n），再遍历第二个集合的所有元素（假设元素数为m），总时间复杂度是O(n + m)，也就是线性时间。

另外要注意，Concat和HashSet自带的Union方法不一样：Union会自动去重，而Concat只是简单把两个集合的元素按顺序拼接，哪怕有重复元素也会保留，这也是两者时间复杂度有差异的原因（Union需要额外的哈希检查去重，而Concat不需要）。

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