Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Турнирлар методи
Турнирлар методи рекурсияга асосланган ва унинг ёрдамида кўплаб масалаларни ечиш мумкин, маълумотлар бўйича биринчи ўтиш натижасида олинган ахборот кейинги про-ютларни енгиллаштиради. Агар биз энг катта қийматни излаш учун ундан фойдалансак, ҳамма элементлари i inn г г it баргли бинар дарахтни тузиш талаб қилинади. Ҳар бир босқичда икки элемент жуфтларга бирлашган бўлиб, улардан энг каттаси оталик релига нусхаланади. Жараён илдиз тугунга етгунча такрорланади. Қайд этилган берилганлар тўплами учун тўлиқ турнир дарахти 1.3. расмда тасвирланган.

Саккиз қийматдан иборат тўплам учун турнир дарахти


N тартибли таққослашлар миқдори ҳисобига рўйхатдаги катталиги бўйича иккинчи элементни топиш алгоритми ишлаб чиқилади. Бунда бизга турнирлар методи ёрдам беради. Ҳар қандай таққослаш натижасида биз «ғолиб» ва «мағлуб»га эга бўламиз. Мағлубларни унутамиз, дарахт бўйлаб юқорига фақат ғолиблар ҳаракат қилади. Энг ката элементдан ташқари ҳар қайси элемент ҳеч бўлмаганда битта таққослашда мағлубиятга учрайди. Шунинг учун турнир дарахтини қуриш учун N — 1 та таққослаш талаб этилади.
Катталиги бўйича иккинчи элемент энг катта элементдан мағлуб бўлиши мумкин. Дарахтдан пастга томон юриш давомида энг катта элементга ютқазган элементлар рўйхатини тузамиз. 1.3.2 бўлимдаги дарахт учун формула бундай элементлар сони [log₂ N] дан ортиб кетмаслигини кўрсатади. Уларнинг дарахт бўйича қидируви [log₂ N] таққослашни талаб қилади; яна [log₂ N] - 1 таққослашлар улардан энг каттасини танлаш учун керак. Ҳаммаси бўлиб бу ишга N + 2[log₂ N] —2 кетади, яъни O(N) та таққослаш.
Турнирлар методи ёрдамида қийматлар рўйхатини саралаш мумкин. 3-бобда турнирлар методига асосланган уюмларни саралашни кўриб чиқамиз.


Қуйи чегаралар
Алгоритм, агар ундан тезроқ ишлайдиган алгоритм мавжуд бўлмаса, оптимал ҳисобланади. Бизнинг алгоритм оптимал эканлигини қандай билишимиз мумкин? Ёки оптимал эмас, фақатгина етарлича яхши бўлиши ҳам мумкин? Бу саволларга жавоб бериш учун биз аниқ масалани ечиш учун керак бўлган амаллар миқдорини энг кам ҳолатда бўлса ҳам билишимиз керак. Бунинг учун масалани ечувчи алгоритмни эмас, балки айнан масалани ўрганиш керак. Натижада ҳосил қилинган қуйи чегара бу масалани ечиш учун керак бўлган иш ҳажмини кўрсатади ва бунга номзод бўлган тезроқ ишловчи ихтиёрий алгоритм баъзи жараёнларга нотўғри ишлов бериши шарт.
Учта сондан иборат рўйхатни саралаш жараёнини таҳлил қилиш учун яна бинар дарахтидан фойдаланамиз. Дарахтнинг ички тугунларини таққосланган элементлар жуфтлиги билан белгилаймиз. Дарахт новдасидан ўтиши таъминланган элементлар рўйхати дарахтнинг мос баргида тасвирланади. Уч элементдан иборат рўйхат учун дарахт 7.4 расмда тасвирланган. Бундай дарахт ечим дарахти деб номланади.