使用C++ STL set求两个无序数组并集的时间复杂度计算疑问

你提供的代码如下：

// C++ program for the union of two arrays using Set
#include <bits/stdc++.h>
using namespace std;
void getUnion(int a[], int n, int b[], int m)
{
 
    // Defining set container s
    set<int> s;

    // Inserting array elements in s
    for (int i = 0; i < n; i++)
      s.insert(a[i]);

    for (int i = 0; i < m; i++)
      s.insert(b[i]);
    cout << "Number of elements after union operation: " << s.size() << endl;
    cout << "The union set of both arrays is :" << endl;
    for (auto itr = s.begin(); itr != s.end(); itr++)
        cout << *itr
             << " "; // s will contain only distinct
                 // elements from array a and b
}

// Driver Code
int main()
{
    int a[9] = { 1, 2, 5, 6, 2, 3, 5, 7, 3 };
    int b[10] = { 2, 4, 5, 6, 8, 9, 4, 6, 5, 4 };

    getUnion(a, 9, b, 10);
}

复杂度推导过程 #

首先明确基础前提：C++ STL的set底层实现为红黑树（平衡二叉搜索树的一种），单次插入、查找操作的时间复杂度均为O(log k)，其中k为set当前存储的元素个数。

我们按代码执行顺序拆分计算各部分的时间开销：

• 第一个循环：插入长度为n的数组a的所有元素
  最坏情况下数组a的所有元素互不重复，插入过程中set的大小从0逐步增长到n，单次插入的最大时间开销为O(log n)，n次插入的总时间复杂度为O(n log n)。如果数组a存在重复元素，插入重复元素时会先执行查找操作，查找的时间复杂度同样为O(log k)，不改变最坏时间复杂度的量级。
• 第二个循环：插入长度为m的数组b的所有元素
  最坏情况下数组b的所有元素既不重复也和数组a的元素完全不重叠，插入过程中set的大小从n增长到n+m。此处取上界计算可得：log(n+m) ≤ log(2*max(m,n)) = log2 + log(max(m,n))，因此m次插入的总时间上界可以表示为O(m log (m+n))，该量级和*O(m log m)*等价，二者仅差常数系数。
• 第三个循环：遍历输出set的所有元素
  红黑树的遍历时间复杂度为O(k)，k为set元素总数，最大为n+m，这个线性阶的开销远小于前面的对数阶开销，计算整体复杂度时可以忽略。

综上，整体最坏时间复杂度可表示为O(n log n + m log m)，它和*O((n+m)log(n+m))*是同阶的时间复杂度，二者只是表述方式不同。

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