Cik daudz papildu atmiņas prasa vārdu krājuma risinājums, neskaitot atgrieztos datus?

Vārdu krājuma (haštabulas) izmantošana prasa papildu atmiņu, kas ir proporcionāla tajā pievienoto unikālo atslēgu skaitam. Ja jums ir N unikāli elementi, atmiņa būs aptuveni O(N), jo katram atslēgai un ar to saistītajai vērtībai tiek piešķirta vieta.

Piemēram, ja jūs izveidojat vārdnīcu, lai skaitītu vārdu atkārtošanās skaitu tekstā, atmiņa pieaugs ar unikālo vārdu skaita pieaugumu. Turklāt vārdnīcas struktūra parasti ietver papildu izmaksas hash vērtību glabāšanai un kolīziju pārvaldībai, bet kopumā, novērtējums O(N) papildu atmiņai ir vispraktiskākais.