List və Set kolleksiyalarında (məsələn, contains metodundan istifadə etməklə) axtarış nə qədər vaxt aparır?

List üçün, contains istifadə edilən axtarışın hesablama mürəkkəbliyi O(n)-dir, burada n siyahıdakı elementlərin sayıdir. Bu, ən pis halda, axtarılan elementin mövcudluğunu müəyyən etmək üçün siyahının bütün elementlərinin yoxlanmasını tələb edir.

Set üçün, contains istifadə edilən axtarışın orta hesabla mürəkkəbliyi O(1)-dir. Bu, elementlərin daxili saxlanması üçün hash cədvəlindən istifadə etməklə əldə edilir. İdeal halda (yaxşı hash funksiyası və kolliziyaların olmaması), axtarış sabit vaxt alır. Ən pis halda (çox kolliziya), mürəkkəblik O(n)-ə yaxınlaşa bilər, amma bu praktiki olaraq nadirdir.