我无法理解以下 C++ 代码的时间复杂度是如何计算的？

Question

以下代码使用 C++ STL 集打印两个未排序数组的并集。
我知道在集合中插入一个元素的时间复杂度是O(log N)，其中N是集合的大小
此代码来自 https://www.geeksforgeeks.org/find-union-and-intersection-of-two-unsorted-arrays/.

// 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);
}

时间复杂度：O(m * log(m) + n * log(n))。
请说明上述时间复杂度是如何计算的

Answer 1

在 set 中插入一个新元素是对数时间（在你的例子中 O(log n) 和 O(log m) ），所以总时间复杂度是 O(m * log(m) + n * log(n)) .

这里a link你可以参考

Answer 2

在 C++ 中，set 是使用自平衡二叉搜索树 (BST) 在内部实现的。这意味着每次将一个新元素插入 set 时，它必须在内部检查这个新元素在 BST 中的正确插入位置，然后重新平衡 BST。这种插入新元素并执行 BST 重新平衡的操作大约需要 O(log(n)) 时间，其中 n 是 BST 中元素的数量。

下面的代码片段运行s n 次，每个 insert 操作在最坏情况下具有 O(log(n)) 时间复杂度，因此下面的时间复杂度一段代码是 O(n * log(n)).

    for (int i = 0; i < n; i++)
      s.insert(a[i]);

现在，上面的代码片段执行后，集合在最坏情况下会有n个元素（如果int a[]中的所有n个元素都是唯一的）。

下面提供的下一个代码片段运行s m 次，每个 insert 操作在最坏的情况下具有 O(log(n + m)) 时间复杂度（因为可能已经有n 个元素在 set 之前下面的循环开始），因此下面这段代码的时间复杂度是 O(m * log(m + n)).

    for (int i = 0; i < m; i++)
      s.insert(b[i]);

在最坏的情况下（如果数组 a[] 中的所有 n 元素和所有 m 数组 b[] 中的元素是唯一的）。因此，下面代码的时间复杂度是 O(n + m)，因为下面的代码访问了内部 BST 中的所有 n + m 个元素。

    for (auto itr = s.begin(); itr != s.end(); itr++)
        cout << *itr
             << " "; // s will contain only distinct
                 // elements from array a and b

所有上述 3 个代码片段运行连续（一个接一个），因此必须添加总时间复杂度才能找到最终时间复杂度。

时间复杂度=O(nlog(n) + mlog(m + n) + (m + n))

以上3项中，nlog(n)和mlog(m + n)项大于(m + n)，因此我们可以省略(m + n)，将时间复杂度写为O(nlog(n) + mlog(m + n)).

我无法理解以下 C++ 代码的时间复杂度是如何计算的？

I can't understand how the time complexity of following c++ code is calculated?

c++

stl

set

data-structures