Քանի լրացուցիչ հիշողություն է պահանջում բառարանի լուծումը, բացի վերադարձվող տվյալներից?

Լեզվագրի (հեշ-թերթի) օգտագործումը պահանջում է լրացուցիչ հիշողություն, որը համեմատական է այն քանակի եզակի բանալիների թվին, որոնք ավելացվում են: Եթե ունեք N եզակի տարրեր, ապա հիշողությունը մոտավորապես կլինի O(N), քանի որ յուրաքանչյուր բանալի և նրա հետ կապված արժեքի համար հատկացվում է տարածք:

Օրինակ, եթե ստեղծում եք բառարան՝ հաշվելու համար, թե քանի անգամ են հանդիպում բառերը տեքստում, ապա հիշողությունը կաճի եզակի բառերի թվի աճի հետ: Բացի այդ, բառարանի կառուցվածքը սովորաբար ներառում է լրացուցիչ ծախսեր հեշ-արժեքների պահպանում և բախումների կառավարում, բայց ընդհանուր առմամբ, O(N) գնահատականը լրացուցիչ հիշողության համար ամենահարմարն է: