Экилик издөө жана сызыктуу издөө
Сызыктуу издөө, ошондой эле ырааттуу издөө катары белгилүү болгон эң жөнөкөй издөө алгоритми. Ал тизмедеги ар бир элементти текшерүү менен тизмедеги көрсөтүлгөн маанини издейт. Бинардык издөө, ошондой эле сорттолгон тизмеде көрсөтүлгөн маанини табуу үчүн колдонулган ыкма. Бинардык издөө ыкмасы текшерилген элементтердин санын эки эсеге кыскартат (ар бир итерацияда), бул тизмедеги берилген нерсени табууга кеткен убакытты кыскартат.
Сызыктуу издөө деген эмне?
Сызыктуу издөө эң жөнөкөй издөө ыкмасы, ал тизмедеги ар бир элементти белгиленген элементти тапканга чейин ырааттуулук менен текшерет. Сызыктуу издөө ыкмасына киргизүү бул ырааттуулук (мисалы, массив, коллекция же сап) жана издөө керек болгон нерсе. Көрсөтүлгөн нерсе берилген ырааттуулуктун ичинде болсо, чыгаруу чын же ырааттуулукта болбосо, жалган болот. Бул ыкма көрсөтүлгөн элемент табылганга чейин тизмедеги ар бир пунктту текшергендиктен, эң начар учурда ал керектүү элементти тапканга чейин тизмедеги бардык элементтерден өтүп кетет. Сызыктуу издөөнүн татаалдыгы o(n). Ошондуктан чоң тизмелерде элементтерди издөөдө колдонуу өтө жай деп эсептелет. Бирок бул абдан жөнөкөй жана ишке ашыруу оңой.
Бинардык издөө деген эмне?
Экилик издөө ошондой эле сорттолгон тизмеде көрсөтүлгөн нерсени табуу үчүн колдонулган ыкма. Бул ыкма изделген элементти тизменин ортосундагы элементтер менен салыштыруудан башталат. Эгерде салыштыруу эки элементтин бирдей экендигин аныктаса, метод токтойт жана элементтин ордун кайтарат. Изделген элемент ортоңку элементтен чоңураак болсо, ал иреттелген тизменин төмөнкү жарымын гана колдонуу менен ыкманы кайра баштайт. Изделген элемент ортоңку элементтен азыраак болсо, ал иреттелген тизменин жогорку жарымын гана колдонуп, ыкманы кайра баштайт. Эгерде изделген элемент тизмеде жок болсо, ыкма аны көрсөткөн уникалдуу маанини кайтарат. Ошондуктан бинардык издөө ыкмасы салыштыруунун натыйжасына жараша салыштырылган элементтердин санын эки эсеге кыскартат (ар бир итерацияда). Демек, бинардык издөө логарифмдик убакытта иштейт, натыйжада o(log n) иштин орточо көрсөткүчү.
Бинардык издөө менен сызыктуу издөөнүн ортосунда кандай айырма бар?
Сызыктуу издөө жана бинардык издөө издөө ыкмалары болгону менен, алардын бир нече айырмачылыктары бар. Экилик издөө сорттолгон тизмелерде иштесе, лайнер издөө сорттолбогон тизмелерде да иштей алат. Тизмени сорттоо жалпысынан n log n болгон орточо иштин татаалдыгына ээ. сызыктуу издөө бинардык издөөгө караганда жөнөкөй жана жөнөкөй. Бирок, сызыктуу издөө, анын o(n) орточо көрсөткүчүнө байланыштуу чоң тизмелер менен колдонуу үчүн өтө жай. Башка жагынан алганда, бинардык издөө чоң тизмелер менен колдонулушу мүмкүн болгон кыйла натыйжалуу ыкма болуп эсептелет. Бирок бинардык издөөнү ишке ашыруу өтө татаал болушу мүмкүн жана изилдөө экилик издөөнүн так кодун жыйырма китептин бешөөнөн гана табууга болорун көрсөткөн.
