Բաժանիր և տիրիր ալգորիթմներ

Առայժմ մեր սովորած տեսակավորման ալգորիթմներն են ընտրանքային տեսակավորումը և մուտքային տեսակավորումը, որոնց վատագույն հաշվողական դժվարությունը $\mathrm{\Theta }(n^2)$‍ է։ Մուտքագրված մեծածավալ զանգվածն այս երկու ալգորիթմները կարող է շատ երկար ժամանակում տեսակավորել։ Այս և հաջորդ տեսանյութերում մենք կծանոթանանք ևս երկու ալգորիթմների հետ՝ միաձուլման տեսակավորում և արագ տեսակավորում, որոնք ավելի արագ են աշխատում։ Միաձուլման տեսակավորումը բոլոր դեպքերում ունի $\mathrm{\Theta }(n\lg n)$‍ հաշվողական դժվարություն, մինչդեռ արագ տեսակավորման լավագույն հաշվողական դժվարությունը $\mathrm{\Theta }(n\lg n)$‍ է, իսկ վատագույնը՝ $\mathrm{\Theta }(n^2)$‍։ Այս աղյուսակը ցույց է տալիս մեր սովորած չորս տեսակավորման ալգորիթմները և դրանց հաշվողական դժվարությունները․

Միաձուլման տեսակավորումն ու արագ տեսակավորումն ունեն ռեկուրսիայի հիման վրա ստեղծված ալգորիթմական ստրատեգիա։ Այս ստրատեգիան՝ Բաժանիր և տիրիր, բաժանում է խնդիրը ենթախնդիրների, որոնք նման են դրան, ռեկուրսիվորեն լուծում է ենթախնդիրները և վերջապես միավորում է դրանք, որպեսզի դրանց օգնությամբ լուծի իրական խնդիրը։ Քանի որ «Բաժանիր և տիրիր» ռազմավարությունը ռեկուրսիվորեն է լուծում ենթախնդիրները, բոլոր ենթախնդիրները պետք է ավելի փոքր լինեն, քան խնդիրը, և ենթախնդիրների համար պետք է լինի առաջին քայլ։ Կարող ենք ասել, որ «Բաժանիր և տիրիր» ալգորիթմը երեք մաս ունի․

Դու հեշտությամբ կարող ես հիշել «Բաժանիր և տիրիր» ալգորիթմի քայլերը՝ որպես բաժանել, տիրել, միավորել։ Ահա թե ինչպես պատկերացնել այն՝ համարելով, որ մի բաժանումը ստեղծում է երկու ենթախնդիր (չնայած «Բաժանիր և տիրիր» ռազմավարության որոշ ալգորիթմներ ստեղծում են ավելին, քան երկուսը)․

Եթե այն ընդլայնենք ևս երկու ռեկուրենտ քայլերի, այսպիսի տեսքի կգա․

Քանի որ «Բաժանիր և տիրիր» ռազմավարությունը ստեղծում է առնվազն երկու ենթախնդիր, «Բաժանիր և տիրիր» ալգորիթմը կատարում է մի քանի ռեկուրենտ կանչ։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։