Une structure de données avec n éléments et avec des opérations O(1) ?

Ici, nous verrons une structure de données avec n éléments et opérations O(1). Par conséquent, l’exécution de l’opération prendra un temps constant.

La structure de données contiendra n éléments (de 0 à n-1). Les données peuvent être dans n'importe quel ordre. L'insertion, la suppression et la recherche prendront un temps O(1).

Pour résoudre ce problème, nous utiliserons un tableau booléen. Cela indiquera si l’élément existe à l’emplacement i. 1 si l'élément existe, 0 sinon.

Algorithme

Initialiser(n)

begin
   fill all elements of the Boolean array as 0
end

Insérer(i)

begin
   set element at index i as 1(true)
end

Supprimer(i)

begin
set element at index i as 0(false)
end

Rechercher(i)

begin
   return item at position i
end

Exemple

//initialization
void init(int n) {
   bool dataStructure[n];
   for (int i = 0; i<n; i++)
      dataStructure[i] = 0;
}
//Insertion
void insert(unsigned i) {
   dataStructure[i] = 1;
}
//Deletion
void delete(unsigned i) {
   dataStructure[i] = 0;
}
//Search
bool search(unsigned i) {
   return dataStructure[i];
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!