Problema saptamanii - Initializare

Cosmin Negruseri
30 august 2010

La unii algoritmi eficienti initializarea memoriei face algoritmul mai incet.

Se cere sa implementati o structura de date ce poate reprezenta o multime de intregi din multimea {0, 1, .., U - 1}. Aveti deja un sir de U intregi ce nu e initializat, deci contine valori oarecare. Veti putea folosi memorie suplimentara proportionala cu numarul de intregi n ce vor fi adaugati in multime. Operatiile de initializare, adaugare si verificare de incluziune trebuie sa se execute in O(1) tot timpul nu doar amortizat (altfel o solutie era sa folosim un hash table).