Problema saptamanii - Initializare

Cosmin Negruseri
30 august 2010

Initializarea memoriei ajunge, in cazul unor algoritmi eficienti, sa incetineasca timpul total de executie. Saptamana asta incercam sa gasim o metoda ce evita aceasta problema.

Gasiti o structura de date ce reprezinta o submultime a multimii {0, 1, ... , U - 1}. Aveti la dispozitie o zona de memorie continua in care incap U intregi care nu e initializata, deci contine valori oarecare. Puteti folosi memorie suplimentara proportionala cu numarul de intregi N ce vor fi adaugati in multime. Operatiile de initializare, adaugare si verificare a incluziunii trebuie sa se execute in O(1) (nu doar amortizat, altfel o solutie este sa folosim un hash table).