List жана Set коллекцияларында издөө (мисалы, contains ыкмасын колдонуу менен) канча убакыт алат?

List үчүн, contains колдонуу менен издөө эсептөө татаалдыгы O(n), анда n — тизмедеги элементтердин саны. Бул эң жаман учурда, издөө үчүн тизмедеги бардык элементтерди карап чыгуу керектиги менен байланыштуу.

Set үчүн, contains колдонуу менен издөө орто эсеп менен O(1) татаалдыгы бар. Бул ички сактоо үчүн хэш таблицасын колдонуу менен жетишилет. Идеалдуу учурда (жакшы хэш функциясы жана кагылышуулар жок болсо), издөө туруктуу убакытты талап кылат. Эң жаман учурда (көп кагылышуулар), татаалдык O(n) жакындашы мүмкүн, бирок бул практикада сейрек кездешет.