Блог

Кто-нибудь знает, возможно ли превратить это из O (m * n) в O (m n)?

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

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

    theSecond.push_back(1);
    theSecond.push_back( -2147483648 );
    theSecond.push_back(3);
    theSecond.push_back(44);
    theSecond.push_back(32);
    theSecond.push_back(1);

    for( int i = 0; i < theFirst.size(); i   )
    {
        for( int x = 0; x < theSecond.size(); x   )
        {
            if( theFirst[i] == theSecond[x] )
            {
                theMatch.push_back( theFirst[i] );
            }
        }
    }
  

Поместите содержимое первого вектора в хэш-набор, такой как std::unordered_set . Это O (m). Просканируйте второй вектор, проверяя, находятся ли значения в unordered_set и ведя подсчет тех, которые есть. Это n поисков хэш-структуры, так что O (n). Итак, O(m n). Если у вас есть l элементов в перекрытии, вы можете посчитать O (l) для добавления их к третьему вектору. std::unordered_set находится в черновике C 0x и доступна в последних версиях gcc, а также существует реализация в boost.

Отредактировано для использования unordered_set

Использование синтаксиса C 2011:

 unordered_set<int> firstMap(theFirst.begin(), theFirst.end());

for (const intamp; i : theSecond) {
   if (firstMap.find(i)!=firstMap.end()) {
     cout << "Duplicate: " << i << endl;
     theMatch.push_back(i);
   }
}
  

Теперь все еще остается вопрос, что вы хотите делать с дубликатами в оригиналах? Явно, сколько раз должно 1 быть в theMatch , 1, 2 или 4 раза?
Это выводит:

 Duplicate: 1
Duplicate: -2147483648
Duplicate: 44
Duplicate: 1
  

Используя это: http://www.cplusplus.com/reference/algorithm/set_intersection /

Я полагаю, вы должны быть в состоянии достичь O(mlogm nlogn) . set_intersection требуется, чтобы входные диапазоны были уже отсортированы). Однако это может работать немного иначе, чем ваше решение для повторяющихся элементов.

Пожалуйста, поправьте меня, если я ошибаюсь, вы предлагаете следующее решение проблемы пересечения: отсортируйте два вектора и продолжайте итерацию в обоих отсортированных векторах таким образом, чтобы мы достигли общего элемента, поэтому общая сложность будет (n * log (n) m * log (m)) (n m) Предполагая, что k * log (k) как сложность сортировки

Я прав? Конечно, сложность будет зависеть от сложности сортировки.

Я бы отсортировал более длинный массив O (n * log (n)), искал элементы из более короткого массива O (m * log (n)). Тогда итого равно O (n * log(n) m * log (n) )

Предполагая, что вы хотите создать theMatch из двух наборов данных, и вас не волнуют сами наборы данных, поместите один из них в unordered_map (доступен в настоящее время в Boost и указан в окончательном проекте комитета для C 11), сопоставляя ключ с целым числом, которое увеличивается при добавлении к, и, следовательно, отслеживает количество раз, когда встречается ключ. Затем, когда вы получаете совпадение с другим набором данных, вы push_back указываете, сколько раз это произошло в первый раз.

Вы можете получить O (n log n m log m), сначала отсортировав векторы, или O (n log n m), создав std::map один из них.

Предостережение: это операции, не сохраняющие порядок, и theMatch они будут выполняться в разных порядках с использованием разных методов. Мне кажется, что порядок, скорее всего, считается произвольным. Если порядок, указанный в приведенном выше коде, необходим, я не думаю, что есть алгоритм лучше.

Редактировать:

Возьмем набор данных A и набор данных B типа Type. Создайте unordered_map<Type, int> .

Просмотрите набор данных A и проверьте каждый элемент, чтобы увидеть, есть ли он на карте. Если нет, добавьте элемент с int 1 на карту. Если это так, увеличьте int . Каждая из этих операций в среднем равна O (1), поэтому этот шаг равен O (len A).

Просмотрите набор данных B и проверьте каждый элемент, чтобы увидеть, есть ли он на карте. Если нет, переходите к следующему. Если это так, push_back поместите элемент в очередь назначения. int — это количество раз, когда это значение встречается в наборе данных A, поэтому сделайте push_back количество раз, когда элемент в A дублирует заданное поведение. Каждая из этих операций в среднем составляет O (1), поэтому этот шаг равен O (len B).

Это обычное поведение. Если вы всегда сталкиваетесь с наихудшим вариантом, вы возвращаетесь к O (m * n). Я не думаю, что есть способ гарантировать O (m n).

Если порядок элементов в результирующем массиве / наборе не имеет значения, то ответ — да.

Для произвольных типов элементов с некоторым определенным порядком наилучшим алгоритмом является O( max(m,n)*log(min(m,n)) ) . Для чисел ограниченного размера лучшим алгоритмом является O(m n) .

• Создайте набор элементов меньшего массива — для произвольных элементов допустима просто сортировка, а для чисел ограниченного размера это должно быть что-то похожее на промежуточную таблицу в числовой сортировке.

• Выполните итерацию по большему массиву и проверьте, находится ли элемент в наборе, созданном ранее — для произвольного элемента двоичный поиск разрешен (что является O(log(min(n,m)) ), а для чисел единственная проверка равна O (1).