Неупорядоченные вопросы

Кто-нибудь может объяснить, как работает неупорядоченный набор? Я также не уверен, как работает набор. Мой главный вопрос - какова эффективность его функции поиска.

Например, каково общее время выполнения этого большого 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];
        }
   }
Источник

2 ответа

unordered_set и все остальные unordered_ структуры данных используют хеширование, как упомянуто @Sean. Хеширование включает в себя амортизированное постоянное время для вставки и близко к постоянному времени для поиска. Хеш-функция, по сути, берет некоторую информацию и выдает из нее число. Это функция в том смысле, что один и тот же вход должен давать одинаковый результат. Однако разные входные данные могут приводить к одному и тому же выходному сигналу, что приводит к столкновению. Поиск гарантированно будет постоянным временем для "идеальной хэш-функции", то есть без коллизий. На практике входной номер берется из элемента, который вы храните в структуре (скажем, его значение, это примитивный тип), и сопоставляет его с местоположением в структуре данных. Следовательно, для данного ключа функция переносит вас в место, где хранится элемент, без необходимости каких-либо обходов или поисков (игнорируя столкновения здесь для простоты), следовательно, с постоянным временем. Существуют различные реализации этих структур (открытая адресация, цепочка и т. Д.). См. Хэш-таблицу, хэш-функцию. Я также рекомендую раздел 3.7 Руководства по разработке алгоритмов Skiena. Теперь, что касается сложности big-O, вы правы в том, что у вас есть O(n) + O(n) + O(размер перекрытия). Поскольку перекрытие не может быть больше, чем меньшее из m и n, общая сложность может быть выражена как O(kN), где N является наибольшим между m и n. Скоро). Опять же, это "лучший случай", без коллизий и с идеальным хешированием.

set а также multi_set с другой стороны, используйте двоичные деревья, поэтому вставки и поиски обычно O (logN). Фактическая производительность хешированной структуры по сравнению с бинарным деревом зависит от N, поэтому лучше всего попробовать два подхода и профилировать их в реалистичном сценарии работы.

Источник

Все типы данных std::unordered_*() используют хеш для поиска. Посмотрите документацию Boost по этому вопросу, и я думаю, вы очень быстро получите понимание.

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

Источник
Другие вопросы по тегам