რამდენი დამატებითი მეხსიერება სჭირდება სიტყვების გარჩევის გადაწყვეტას, დაბრუნებული მონაცემების გარეშე?

სიტყვის სია (ჰეშ-ცხრილი) მოითხოვს დამატებით მეხსიერებას, რომელიც პროპორციულია მასში დამატებული უნიკალური გასაღებების რაოდენობასთან. თუ გაქვთ N უნიკალური ელემენტი, მეხსიერება იქნება დაახლოებით O(N), რადგან თითოეულ გასაღებს და მის დაკავშირებულ მნიშვნელობას გამოყოფილი ადგილი აქვს.

მაგალითად, თუ ქმნით სია სიტყვების რაოდენობის გამოთვლისთვის ტექსტში, მეხსიერება გაიზრდება უნიკალური სიტყვების რაოდენობის ზრდასთან ერთად. გარდა ამისა, სია ჩვეულებრივ შეიცავს დამატებით ხარჯებს ჰეშ მნიშვნელობების შენახვაზე და კოლიზიების მართვაზე, მაგრამ ზოგადად, O(N) შეფასება დამატებითი მეხსიერებისთვის ყველაზე პრაქტიკულია.