Informatyka MIMUW

W przypadku gdy zbiór, który przechowujemy, pochodzi z niewielkiego uniwersum (na przykład elementy zbioru to liczby z zakresu \( 1,\ldots,n \)), możemy wszystkie operacje słownikowe (dodaj, usuń, szukaj) wykonać znacznie szybciej i prościej.

Dla uniwersum \( 1,\ldots,n \) zbiór możemy reprezentować przez tablicę \( n \)-elementową. Początkowo w każdej komórce tablicy wpisujemy wartość false.

• dodanie elementu \( i \) do zbioru wymaga jedynie ustawienia wartości \( i \)-tej komórki na true,
• analogicznie, usunięcie elementu \( i \) do zbioru wymaga ustawienia wartości \( i \)-tej komórki na false,
• sprawdzenie, czy element \( i \) należy do zbioru, wykonujemy przez sprawdzenie stanu \( i \)-tej komórki.

Wszystkie powyższe operacje możemy wykonać używając stałej liczby kroków.