Je dois trouver le nombre d'éléments uniques dans une liste de n éléments. J'ai utilisé set et cela a été accepté, mais lorsque j'ai utilisé unordered_set dans l'un des cas, le délai est dépassé, comment est-ce possible?
Code utilisant 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;
}
Code en utilisant 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;
}
3 Réponses :
Le scénario de test contient des valeurs très mal hachées, avec de nombreuses collisions.
La complexité du pire des cas pour l'insertion dans unordered_set est linéaire dans la taille de l'ensemble.
L'insertion dans un ensemble est logarithmique dans le pire des cas.
set utilise un arbre rouge noir en interne donc il effectue des opérations en interne comme un BST , et il crée un arbre équilibré donc la recherche est environ temps logarithmique bien sûr dans tous les cas, mais l'insertion dans un unordered_set dépend des données utilisées et de la "fonction de hachage interne" qui détermine en fait le nombre de collisions dans le ensemble de hachage, il est donc possible qu'en raison d'un nombre plus élevé de collisions dues à une entrée particulière, il puisse ne pas gérer le grand nombre de collisions car la gestion des collisions prend également du temps car elle peut utiliser l'une des 2 méthodes standard
L'opération insert () unordered_set a la pire complexité temporelle de O (n), tandis que dans le cas de order_set, la complexité temporelle est O (log (n)) car elle maintient l'auto-équilibrage BST après chaque opération. Je vous recommande de parcourir la documentation ci-dessous par référence CPP et vous pouvez trouver toutes les informations reliées à c ++.
Références: Pour unordered_set: insert ()
(1) https://en.cppreference.com/w/ cpp / container / unordered_set / insert
Pour order_set: insert ()
(2) https://en.cppreference.com/w/ cpp / container / set / insert
J'espère que cela vous aidera. bon codage ..