std::inplace_merge 的复杂性

Question

所以我有两个排序向量，我想将它们合并为一个排序向量，而不使用额外的向量。

由于有这种情况我无法使用std::merge，所以我尝试了std::inplace_merge。

我有这个函数，它接受两个向量和两个数字m和n，它们是每个向量中的元素数量。这是我解决这个问题的方法：

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
         auto it = std::remove_if(std::execution::par, nums1.begin() + m, nums1.end(), 
             [](const int val)
             {
                 return val == 0;
             }
         );
         nums1.erase(it, nums1.end());

        nums1.insert(nums1.end(), nums2.begin(), nums2.end());
        std::inplace_merge(std::execution::par, nums1.begin(), nums1.begin() + nums1.size() - nums2.size(), nums1.end());
    }

案例示例

vec 1 = [1,2,3,0,0,0]
m = 3
vec2 = [2,5,6]
n = 3

预期输出：

[1, 2, 2, 3, 5, 6]

我尝试寻找空间和时间复杂度

一切正常，现在我想要的是找出时间和空间复杂度。 我想出了以下几点：

空间复杂度就是总向量的大小，对吗？在这种情况下，我相信它是 O(m + n)

至于时间复杂度， std::remove_if 最多需要 m ，因此 std::vector::erase 和 std::vector::insert 将需要 n （第二个向量），最后 std::inplace_merge 需要 O(n log n)。

所以最后我们有 O(n log n + 2m + n)，我对吗？

Answer 1

你的计算大部分是正确的，但是：

1. 你正在混合你的参数；您使用的

   n

   会改变一个向量中的元素数量和组合向量中的元素数量之间的含义。
2. 传统上，big-O 表示法会忽略常数因子，以及任何与更高的 big-O 表达式相形见绌的项。所以

   2m

   与

   m

   是一样的，如果

   n

   是

   m

   的超集，那么

   n log n

   意味着您完全忽略

   2m

   术语。
3. 类似地，您将实际上相同事物的术语组合在一起（因此为

   m

   使用

   nums1

   并为

   n

   使用

   nums2

   是毫无意义的；

   n log n

   的工作是在 combined 大小上；您可以通常忽略两个输入之间的区别）。
4. 你的空间复杂度（如果你不放弃常数因子）可以说是

   O(m + 2n)

   ，因为你没有消耗第二个向量中的元素，你正在复制它们（所以你最终得到了每个元素的一个副本

   nums1

   ，以及

   nums2

   中每个元素两个）。但当然，根据 #2/#3，这比您使用的大 O 表示法更详细。

因此，用大 O 术语来说，您可以将时间复杂度简单地表示为

O(n log n)

（

n

是两个输入的组合大小），将空间复杂度表示为

O(n)

（它需要最多

2n

空间） ，如果

nums1

为空并且

nums2

包含所有数据，但常数因子对于大 O 来说并不重要）。随着输入规模的增长，这些是主导术语，从理论角度来看，其他一切都变得无关紧要（即使这些实际问题在现实生活中实际上可能很重要）。