- Сызыктуу издөөнү өз сөзүңүз менен аныктап, түшүндүрүңүз
- «Сызыктуу издөө» сыяктуу негизги терминдерди так колдонуңуз
- Үйрөнгөнүңүздү жаңы мисалдарга жана суроолорго колдонуңуз
- Бул темада окуучулар кетирген кеңири таралган каталардан сактаныңыз
Бардык чечимдер бирдей эмес: айрымдары миллиондогон тизмеден ысымды жыйырма кадамда табат, айрымдарына миллион керек. GCSE деңгээлинде сиз жөн гана иштеген чечимди жазуудан жакшы чечимдерди жазууга өтөсүз. Бул бөлүм классикалык издөө жана сорттоо алгоритмдерин — жана кайсынысы эң жакшы экенин кантип өлчөө керектигин камтыйт.
Бул сабак сызыктуу издөөгө арналат: ар бир элементти бирден текшерип, элементтерди табыңыз.
Ар бир элементти бирден текшерип, элементтерди табыңыз.
Негизги идеялар
Экилик издөө сорттолгон маалыматты талап кылат
Экилик издөө сызыктуу издөөдөн бир топ ылдам — миллион элемент үчүн болжол менен 20 салыштыруу — бирок ал тизме алдын ала сорттолгон болсо гана иштейт. Сорттоонун да өзүнүн чыгымы бар, ошондуктан сорттолбогон маалыматта бир жолку издөө үчүн сызыктуу издөө дагы деле жеңип чыгышы мүмкүн. Туура алгоритм теорияга эмес, кырдаалга жараша тандалат.
Эң начар учур маанилүү
Алгоритмге бакыт жылмайып, максатты биринчи аракетте таап алышы мүмкүн, бирок инженерлер эң начар учурга — мүмкүн болгон эң жай иштөөгө — план түзүшөт. Big-O ушул өсүштү сүрөттөйт: O(n) киргизилген маалымат эки эсе өскөндө убакыт болжол менен эки эсе өсөт дегенди билдирет, ал эми O(n²) киргизилген маалымат эки эсе өскөндө убакыт болжол менен төрт эсе өсөт дегенди билдирет.
Термин — сызыктуу издөө: Максат табылмайынча тизмедеги ар бир элементти бирден текшерүү. Жөнөкөй, сорттолбогон тизмелерде иштейт, бирок чоң тизмелерде жай.
[1, 3, 5, 7, 9, 11, 13] сорттолгон тизмесинде 7ни табуу үчүн экилик издөөнү колдонуңуз.
low = 0, high = 6. Ортоңку индекс = (0 + 6) // 2 = 3. 3-индекстеги элемент 5. 5, 7ден кичине, ошондуктан сол жарымын алып салабыз: low 4 болот. Ортоңку индекс = (4 + 6) // 2 = 5. 5-индекстеги элемент 11. 11, 7ден чоң, ошондуктан оң жарымын алып салабыз: high 4 болот. Ортоңку индекс = (4 + 4) // 2 = 4. 4-индекстеги элемент 7. Табылды — 7, болгону 3 салыштыруудан кийин 4-индексте.
Жооп: Экилик издөө 7ни 4-индексте 3 салыштырууда табат; сызыктуу издөөгө 4 салыштыруу керек болмок.
- Сорттолбогон тизмеде экилик издөөнү колдонуу Түзөтүү: тизмени алгач сорттоңуз же сызыктуу издөөнү колдонуңуз — сорттолбогон маалыматта экилик издөө жөн гана жай эмес, туура эмес жооп берет.
- Тизме индекстери 0дөн башталарын унутуу Түзөтүү: 7 элементтүү тизмеде акыркы индекс 6 — бирге жаңылышуулар классикалык сынак тузагы, ошондуктан кылдаттык менен изилдеңиз.
Практика
50 — максат акыркы болсо же жок болсо ар бир элемент текшерилиши керек.
Болжол менен 20 — ар бир кадам калган элементтерди экиге бөлөт, ошондуктан миллион болжол менен 20 жолу экиге бөлүү менен бирөөгө чейин азаят.
Тизме сорттолбосо, экилик издөөгө алгач аны сорттоо керек — бул сорттоо чыгымы бир жолку издөөдөгү ылдам издөөдөн ашып кетиши мүмкүн.
O(n²) — киргизилген маалымат эки эсе өскөндө төрт эсе өсүү квадраттык өсүштүн белгиси.
Тез текшерүү
Төмөнкүлөрдүн кайсынысы "сызыктуу издөө"нү эң жакшы аныктайт?
Туурабы же туура эмес: экилик издөө ар дайым эң мыкты издөө алгоритми.
[5, 3, 8, 1] тизмесинде көбүктүү сорттоонун бир өтүүсүн изилдеңиз. Андан кийин тизме кандай болот?
- Сызыктуу издөө: ар бир элементти бирден текшерип, элементтерди табыңыз.
- Экилик издөө сорттолгон маалыматты талап кылат: Экилик издөө сызыктуу издөөдөн бир топ ылдам — миллион элемент үчүн болжол менен 20 салыштыруу — бирок ал тизме алдын ала сорттолгон болсо гана иштейт.
- Экилик издөө: Максатты табуу үчүн сорттолгон тизмени кайра-кайра экиге бөлүү — ортосундагы элемент менен салыштырып, максатты камтый албаган жарымын алып салуу.
- Сак болуңуз: сорттолбогон тизмеде экилик издөөнү колдонуу