Мундарижа Кириш

1.5.2. Алгоритм самарадорлигининг қуйи чегараси

Алгоритм оптимал бўлади агар ундан тез ишловчи алгоритм мавжуд бўлмаса. Алгоритмимиз оптималлигини қандай билиш мумкин? Ёки балки у оптималмасдир, лекин етарлича яхшими? Бу саволларга жавоб бериш учун биз аниқ масалани ечиш учун керак бўлган энг кичик амаллар сонини билишимиз керак. Бунинг учун биз масалани ечувчи алгоритмни эмас айнан масалани ўрганишимиз керак. натижада олинган қуйи чегаралар уш бу масалани ечиш учун керак бўлган иш ҳажмини кўрсатади ва исталган беллашувчи уни тез ечувчи алгоритм айрим вазиятларни бошқача қайта ишлашга мажбурлигини кўрсатади.

Учта сондан иборат рўйхатни саралаш жараёнини таҳлил қилиш учун яна бинар дарахтдан фойдаланамиз. Дарахтнинг ички тугунларни солиштириладиган элементлар жуфти билан белгилаймиз. Ушбу дарахт шохи бўйича ўтишни таъминловчи элементлар тартиби дарахтнинг мос баргида тавирланади. Уч элементдан иборат рўйхат учун дарахт 1.4 рамда келтирилган. Бундай дарахт ечим дарахти дейилади.

1.4-расм. Уч элементли рўйхат учун ечим дарахти

Бутун саралаш алгоритми қандай элементларни солиштришига боғлиқ равишда ўз ечим дарахтини тузади. Ечим дарахтидаги илдиздан япроққача энг узун йўл энг ёмон ҳолга мос келади. Энг яхши ҳолга энг қисқа йўл мос келади. Ўртача ҳолат ечим дарахтидаги қирралар сонининг япроқлар нисбатига айтилади. Бир қарашда ечим дарахтини чизиш ва керакли сонларни санаш арзимайди. 10 та сонни саралашдаги ечим дарахтини тасаввур қилинг. Айтилганидек, мумкин бўлган тартиблар сони 3 628 800 га тенг. Шу сабабли дарахтда камида 3 628 800 япроқлар бўлади ёки ундан ҳам кўп бўлиши мумкин. Бундай дарахтда 22 дан кам бўлмаган даража бўлиши керак.

Алгоритм қийинлиги учун ечим дарахти ёрдамида қандай қилиб чегараларни олиш мумкин? Биламизки, коррект алгоритм исталган маълумотлар рўйхатини, ундаги элементларнинг бошланғич тартибидан қатъий назар, тартиблаши керак. Исталган кирувчи қийматлар алмаштирилишларда битта япроқ бўлиши шарт. Бу шуни билдирадики, ечим дарахтида N! Дан кам бўлмаган япроқлар бўлиши керак. агар алгоритм ҳақиқатан самарадор бўлса, у ҳолда ҳар бир алмаштириш бир марта содир бўлади. N! Япроқли дарахтда нечта даража бўлиши керак? Биз кўрдикки, ҳар бир навбатдаги даражада аввалгисидан кўра икки баравар кўп тугун мавжуд. К даражадаги тугунлар сони 2^K-1 га тенг, шунинг учун бизнинг ечим дарахтимизда L даража бўлади. Бунда L – энг кичик бутун сон бўлиб, N!<2^L-1 ўринли. Ушбу тенгсизликни логарифмлаб қуйидагини ҳосил қиламиз:

L нинг энг кичик қийматини топиш учун факториалдан қутилиш мумкинми? Факториалнинг хоссасига мурожаат қиламиз:

(1.5) тенгликдан фойдалансак



(1.22) тенгликдан ҳосил қиламиз





Бу шуни билдирадики саралаш учун L ечим дарахтининг минимал чуқурлиги тартибга эга. Энди биз биламизки исталган O(N logN) тартибдаги саралаш алгоритми энг яхши ҳисобланади ва уни оптимал дейиш мумкин. Шунга қарамай, биламизки исталган O(N logN) амалдан тез ишлайдиган алгоритм тўғри ишлай олмайди.