набор vs неупорядоченный набор! Что лучше использовать?

Question

Мне нужно найти количество уникальных элементов в списке из n элементов. Я использовал набор, и он был принят, но когда я использовал unordered_set в одном из случаев, время превышено. Как это возможно?

Код с использованием набора

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
set<int> s;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
s.insert(x);
}
cout << s.size() << "\n";
return 0;
}

Код с использованием Unordered_set

#include <bits/stdc++.h>
 using namespace std;
 int main()
 {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 unordered_set<int> s;
 int n;
 cin >> n;
 for (int i = 0; i < n; i++)
 {
 int x;
 cin >> x;
 s.insert(x);
 }
 cout << s.size() << "\n";
 return 0;
 }

Answer 1

set использует красно-черное дерево внутри, поэтому он выполняет внутренние операции так же, как BST, и делает balanced tree, так что поиск примерно logarithmic time наверняка в любом случае, но вставка в unordered_set зависит от используемых данных и «внутренней функции ha sh», которая фактически определяет количество столкновений в наборе ha sh, поэтому возможно, что из-за большего количества конфликтов из-за определенного ввода , он может не справиться с большим количеством коллизий, потому что обработка коллизий также требует времени, потому что он может использовать любой из 2 стандартных методов

Answer 2

unordered_set операция insert () имеет наихудшую временную сложность O (n), в то время как в случае order_set временная сложность равна O (log (n)), поскольку она поддерживает самобалансирующийся BST после каждой операции. Я рекомендую вам go через приведенную ниже документацию по CPP -ссылке, и вы можете найти всю информацию, выпущенную для c ++.

Ссылки: Для unordered_set: insert ()

(1) https://en.cppreference.com/w/cpp/container/unordered_set/insert

Для order_set: insert ()

(2) https://en.cppreference.com/w/cpp/container/set/insert

Надеюсь, это поможет ... счастлив кодирование ..

Answer 3

Тестовый пример содержит значения, которые имеют sh очень плохо, с множеством коллизий.
Наихудшая сложность для вставки в unordered_set линейна по размеру набора.
Вставка в set - это логарифмический c в худшем случае.