რამდენი დრო სჭირდება ძიებას (მაგალითად, contains მეთოდის გამოყენებით) List და Set კოლექციებში?

Listთვის, contains გამოყენებით ძიების კომპიუტერული სირთულე არის O(n), სადაც n არის ელემენტების რაოდენობა სიაში. ეს დაკავშირებულია იმასთან, რომ ყველაზე უარესი შემთხვევა მოითხოვს ყველა ელემენტის გადამოწმებას სიისთვის, რათა დადგინდეს, არის თუ არა საძიებო ელემენტი.

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