Kaip įvertinti paieškos efektyvumą pagal raktą duomenų struktūroje Set?

Duomenų struktūroje Set paieškos efektyvumas paprastai vertinamas kaip O(1) vidutiniškai, jei Set yra įgyvendintas naudojant žemės maišos lentelę (pavyzdžiui, HashSet Swift arba NSSet Objective-C). Tai reiškia, kad paieška vyksta labai greitai, nepriklausomai nuo rinkinio dydžio.

Tačiau blogiausiu atveju (pavyzdžiui, su daugeliu maišos kolizijų), sudėtingumas gali sumažėti iki O(n). Jei Set yra įgyvendintas naudojant subalansuotą medį (pavyzdžiui, TreeSet kituose kalbose), tada paieška turės sudėtingumą O(log n).

Todėl paieškos efektyvumas priklauso nuo konkrečios įgyvendinimo, tačiau standartinių žemės maišos pagrindu sukurtų Set paieška pagal raktą dažniausiai yra labai greita ir artima pastoviam laikui.