为什么std :: unordered_set operator ==()N ^ 2的复杂性？

Question

我有两个矢量v1和v2类型std::vector<std::string>.两个向量都具有唯一值,如果值比较相等但不依赖于向量中出现的顺序值,则应比较相等.

我假设两组类型std::unordered_set是更好的选择,但我认为它是两个向量.

不过,我想了所需的顺序不区分大小写的比较,我就用operator==从std::unordered_set通过复制两个std::unordered_set.非常喜欢这样:

bool oi_compare1(std::vector<std::string> const&v1,
                 std::vector<std::string> const&v2)
{
    std::unordered_set<std::string> tmp1(v1.begin(),v1.end());
    std::unordered_set<std::string> tmp2(v2.begin(),v2.end());
    return tmp1 == tmp2;
}

在分析时我注意到这个功能耗费了大量时间,所以我检查了doc并看到了O(n*n)这里的复杂性.我很困惑,我很期待O(n*log(n)),比如我提出的以下天真的解决方案:

bool oi_compare2(std::vector<std::string> const&v1,
                 std::vector<std::string> const&v2)
{
    if(v1.size() != v2.size())
        return false;
    auto tmp = v2;
    size_t const size = tmp.size();
    for(size_t i = 0; i < size; ++i)
    {
        bool flag = false;
        for(size_t j = i; j < size; ++j)
            if(v1[i] == tmp[j]){
                flag = true;
                std::swap(tmp[i],tmp[j]);
                break;
            }
        if(!flag)
            return false;
    }
    return true;
}

为什么O(n*n)复杂性std::unordered_set和是否有可用于订单不敏感比较的功能构建？

编辑----基准

#include <unordered_set>
#include <chrono>
#include <iostream>
#include <vector>

bool oi_compare1(std::vector<std::string> const&v1,
        std::vector<std::string> const&v2)
{
    std::unordered_set<std::string> tmp1(v1.begin(),v1.end());
    std::unordered_set<std::string> tmp2(v2.begin(),v2.end());
    return tmp1 == tmp2;
}
bool oi_compare2(std::vector<std::string> const&v1,
                std::vector<std::string> const&v2)
{
    if(v1.size() != v2.size())
        return false;
    auto tmp = v2;
    size_t const size = tmp.size();
    for(size_t i = 0; i < size; ++i)
    {
        bool flag = false;
        for(size_t j = i; j < size; ++j)
            if(v1[i] == tmp[j]){
                flag = true;
                std::swap(tmp[i],tmp[j]);
                break;
            }
        if(!flag)
            return false;
    }
    return true;
}

int main()
{
    std::vector<std::string> s1{"1","2","3"};
    std::vector<std::string> s2{"1","3","2"};
    std::cout << std::boolalpha;
    for(size_t i = 0; i < 15; ++i)
    {
        auto tmp1 = s1;
        for(auto &iter : tmp1)
            iter = std::to_string(i)+iter;
        s1.insert(s1.end(),tmp1.begin(),tmp1.end());
        s2.insert(s2.end(),tmp1.begin(),tmp1.end());
    }
    std::cout << "size1 " << s1.size() << std::endl;
    std::cout << "size2 " << s2.size() << std::endl;

    for(auto && c : {oi_compare1,oi_compare2})
    {
        auto start = std::chrono::steady_clock::now();
        bool flag = true;
        for(size_t i = 0; i < 10; ++i)
            flag = flag && c(s1,s2);
        std::cout << "ms=" << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count() << " flag=" << flag << std::endl;
    }
    return 0;
}

给

size1 98304
size2 98304
ms=844 flag=true
ms=31 flag=true

- >天真的进近方式更快.

对于所有Complexity O(N*N)专家来说......让我来看看这种天真的方法.我有两个循环.第一个循环从i=0大小运行到N.内循环从j = i !!!!!!调用 N.在语言中,它意味着我称内循环N次.但由于起始索引j = i !!!!,内循环的复杂性是log(n).如果你仍然不相信我从基准计算复杂性,你会看到......

EDIT2 ---生活在WANDBOX上 https://wandbox.org/permlink/v26oxnR2GVDb9M6y

Answer 1

由于unordered_set是使用hashmap构建的,因此比较lhs == rhs的逻辑将是:

• 检查lhs和rhs的大小,如果不相等,则返回false
• 对于lhs中的每个项目,在rhs中找到它,并进行比较

对于hashmap,在最坏情况下rhs中项目的单个查找时间复杂度将为O(n).因此最坏的情况时间复杂度将是O(n ^ 2).但通常情况下,您会得到O(n)的时间复杂度.