List va Set kolleksiyalarida qidiruv (masalan, contains metodidan foydalanib) qancha vaqt oladi?

List uchun, contains yordamida qidirish hisoblash murakkabligi O(n), bu yerda n ro'yxatdagi elementlar soni. Bu, eng yomon holatda, qidirilayotgan element mavjudligini aniqlash uchun ro'yxatdagi barcha elementlarni tekshirish zarurligi bilan bog'liq.

Set uchun, contains yordamida qidirish o'rtacha O(1) hisoblash murakkabligiga ega. Bu, elementlarning ichki saqlash uchun hash jadvali ishlatilishi bilan erishiladi. Ideal holatda (yaxshi hash funktsiyasi va kolliziyalar yo'qligi), qidirish doimiy vaqt oladi. Eng yomon holatda (ko'p kolliziyalar), murakkablik O(n) ga yaqinlashishi mumkin, ammo bu amalda kam uchraydi.