De ce contează?
La începutul orei, profesorul nu citește toți cei 30 de elevi de pe listă ca să vadă dacă Maria e prezentă. El are o coloană cu o bifă în dreptul fiecărui nume: 1 dacă elevul e în clasă, 0 dacă lipsește. Ca să afle dacă Maria e prezentă, sare direct la rândul ei și se uită la o singură căsuță — nu reparcurge toată lista. Indiferent câți elevi caută, fiecare verificare e o singură privire. Exact asta face un vector caracteristic.
Intuiția
Ai o mulțime de valori dintr-un domeniu cunoscut (de exemplu numere între 0 și
V). Construiești un vector car în care car[x] = 1 dacă x apare în mulțime și
car[x] = 0 altfel. Indexul este valoarea, iar conținutul îți spune doar
„prezent / absent”. Întrebarea „aparține X mulțimii?” devine atunci o singură
citire: te uiți la car[X].
Cheia e că, după o singură marcare (car[x] = 1), nu mai cauți niciodată: orice
întrebare „aparține X?” se reduce la a citi car[X] — o singură poziție, în
O(1), oricâte întrebări ai.