blob: 32e9a16a12f0cf50cb22c5fbbfc2bef09083360c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)$)
|
