0

谁能解释一下无序集是如何工作的？我也不确定一组是如何工作的。我的主要问题是它的查找功能的效率是多少。

例如，这个总的大 O 运行时间是多少？

    vector<int> theFirst;
    vector<int> theSecond;
    vector<int> theMatch;

    theFirst.push_back( -2147483648 );
    theFirst.push_back(2);
    theFirst.push_back(44);


    theSecond.push_back(2);
    theSecond.push_back( -2147483648 );
    theSecond.push_back( 33 );


    //1) Place the contents into a unordered set that is O(m). 
    //2) O(n) look up so thats O(m + n). 
    //3) Add them to third structure so that's O(t)
    //4) All together it becomes O(m + n + t)
    unordered_set<int> theUnorderedSet(theFirst.begin(), theFirst.end());

    for(int i = 0; i < theSecond.size(); i++) 
    {
        if(theUnorderedSet.find(theSecond[i]) != theUnorderedSet.end()) 
        {
        theMatch.push_back( theSecond[i] );
        cout << theSecond[i];
        }
   }
4

2 回答 2

4

unordered_set和所有其他unordered_正如@Sean 所提到的，数据结构使用散列。散列涉及用于插入的摊销常数时间，以及用于查找的接近常数时间。哈希函数本质上是获取一些信息并从中产生一个数字。从某种意义上说，它是一个函数，相同的输入必须产生相同的输出。但是，不同的输入可能会导致相同的输出，从而导致所谓的冲突。对于“完美的散列函数”，即没有冲突的函数，查找将保证是恒定的时间。在实践中，输入数字来自您存储在结构中的元素（比如它的值，它是一个原始类型）并将其映射到数据结构中的某个位置。因此，对于给定的密钥，该函数将您带到存储元素的位置，无需任何遍历或搜索（为简单起见，此处忽略碰撞），因此时间恒定。这些结构有不同的实现（开放寻址、链接等）。请参阅哈希表，哈希函数。我还推荐Skiena的The Algorithm Design Manual的第 3.7 节。现在，关于大 O 复杂性，你是对的，你有 O(n) + O(n) + O（重叠大小）。由于重叠不能大于 m 和 n 中的较小者，因此整体复杂度可以表示为 O(kN)，其中 N 是 m 和 n 之间的最大值。很快）。同样，这是“最佳情况”，没有冲突，并且具有完美的散列。

setmulti_set另一方面，使用二叉树，因此插入和查找通常是 O(logN) 。散列结构与二叉树的实际性能取决于 N，因此最好尝试这两种方法并在实际运行场景中对其进行分析。

于 2011-06-02T08:22:50.880 回答
2

所有的 std::unordered_*() 数据类型都使用散列来执行查找。查看 Boost 关于该主题的文档，我认为您会很快获得理解。

http://www.boost.org/doc/libs/1_46_1/doc/html/unordered.html

于 2011-06-01T17:08:59.703 回答