diff options
Diffstat (limited to 'semestre 3/structures des données/10- Ensemble, partition, file de priorité fusionnable.md')
| -rw-r--r-- | semestre 3/structures des données/10- Ensemble, partition, file de priorité fusionnable.md | 21 |
1 files changed, 21 insertions, 0 deletions
diff --git a/semestre 3/structures des données/10- Ensemble, partition, file de priorité fusionnable.md b/semestre 3/structures des données/10- Ensemble, partition, file de priorité fusionnable.md new file mode 100644 index 0000000..32e9a16 --- /dev/null +++ b/semestre 3/structures des données/10- Ensemble, partition, file de priorité fusionnable.md @@ -0,0 +1,21 @@ +--- +tags: + - sorbonne + - informatique + - structure-des-données +semestre: 3 +--- +## Ensemble +Opérations sur les ensembles : +- insertion +- suppression +- vérification +- union +- intersection + +On utilise une hash table sans valeur pour représenter un ensemble non ordonnée +|> permet d'être en $O(1)$ sur la majorité des opérations, l'union est en $O(n)$ et l'intersection en $O(n_1+n_2)$ +|> besoin de réimplémenter la hash table pour enlever la valeur + +On peut utiliser des AVL si on cherche à avoir un ordre +|> plus lent que la hash table (on est en $O(\log n)$)
\ No newline at end of file |