主页 / coding / 问题 / 77788966
Accepted
IRP_HANDLER
Asked: 2024-01-10 02:24:00 +0800 CST

std::inplace_merge 的复杂性

  • 772

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

由于存在这种情况，我无法使用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)，我对吗？

c++

1 个回答

  1. Best Answer

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

    1. 你正在混合你的参数；您n使用的 改变一个向量中的元素数量和组合向量中的元素数量之间的含义。
    2. 传统上，大 O 表示法会忽略常数因子以及任何与更高的大 O 表达式相形见绌的项。So 与2m是同一件事m，如果n是 的超集m，则n log n意味着您2m完全忽略该术语。
    3. 类似地，您组合实际上是同一事物的术语（因此mfornums1和nfornums2是相当没有意义的；n log n工作在于组合大小；您通常会忽略两个输入之间的区别）。
    4. 您的空间复杂度（如果您没有删除常数因子）可以说是O(m + 2n)，因为您没有消耗第二个向量中的元素，而是复制它们（因此您最终会得到 中每个元素的一个副本nums1，以及 中每个元素的两个副本)中的每个元素nums2。但当然，根据 #2/#3，这比您使用的大 O 表示法更详细。

    因此，用大O术语来说，您可以简单地将时间复杂度表示为O(n log n)（n两个输入的组合大小），将空间复杂度表示为O(n)（它需要2n空间，如果nums1为空并nums2包含所有数据，但常数因子对大O来说无关紧要）。随着输入规模的增长，这些是主导术语，从理论角度来看，其他一切都变得无关紧要（即使这些实际问题在现实生活中可能实际上很重要）。

    请注意，在实践中，std::inplace_merge如果可能，将尝试分配临时空间，如果成功，时间复杂度（就所需的比较次数而言）会下降到O(n)，因此实际使用的空间可能会高于您的预期，而时间可能比预期增长得慢。

    • 3

相关问题