基于列表的不相交集合weighted-union时间复杂度疑问

你纠结的核心点是把单次合并时修改的指针数当成了复杂度的衡量标准，但实际上复杂度分析看的是所有操作的总工作量，以及平摊到单次操作的成本，而非单次操作的瞬时开销。

先明确Weighted-Union的规则 #

每次合并两个集合时，把较短的列表整个附加到较长列表的代表元素上，此时只需要修改短列表中所有元素的指针，让它们指向长列表的代表。

单个元素的指针修改次数才是关键 #

别盯着某次合并改了多少个指针，要看单个元素一生被修改几次指针：

• 一个元素的指针被修改，只有当它所在的集合作为「短列表」被合并到更大的集合时才会发生。
• 每次被合并后，它所在的集合大小至少翻倍（如果是两个等长集合合并，大小直接翻倍；如果是一长一短，短集合并入长集后，新集合大小是两者之和，肯定大于原短集的两倍）。
• 假设总共有n个元素，一个元素从单元素集合开始，最多经过log₂n次合并，所在集合就能达到n的规模（因为每次至少翻倍）。也就是说，每个元素的指针最多被修改log₂n次。

总复杂度与摊还复杂度的推导 #

• n次合并的总复杂度：n个元素，每个最多被修改log n次，总指针修改次数就是n × log n，也就是O(n log n)。
• 单次合并的摊还复杂度：把总工作量n log n平摊到n次合并操作上，平均每次操作的成本就是O(log n)。

对你举的例子的解释 #

比如合并两个4元素集合时，确实要修改4个指针，但这种规模的合并只会发生n/8次（n=8时仅1次）；而修改1个指针的合并会发生n/2次，修改2个指针的合并发生n/4次。把所有这些操作的工作量加起来，总次数刚好是O(n log n)，平摊到每次合并就是O(log n)。

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