If you're seeing this message, it means we're having trouble loading external resources on our website.

Եթե գտնվում ես վեբ զտիչի հետևում, խնդրում ենք համոզվել, որ *.kastatic.org և *.kasandbox.org տիրույթները հանված են արգելափակումից։

Հիմնական նյութ

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

Առայժմ մեր սովորած տեսակավորման ալգորիթմներն են ընտրանքային տեսակավորումը և մուտքային տեսակավորումը, որոնց վատագույն հաշվողական դժվարությունը Θ(n2) է։ Մուտքագրված մեծածավալ զանգվածն այս երկու ալգորիթմները կարող է շատ երկար ժամանակում տեսակավորել։ Այս և հաջորդ տեսանյութերում մենք կծանոթանանք ևս երկու ալգորիթմների հետ՝ միաձուլման տեսակավորում և արագ տեսակավորում, որոնք ավելի արագ են աշխատում։ Միաձուլման տեսակավորումը բոլոր դեպքերում ունի Θ(nlgn) հաշվողական դժվարություն, մինչդեռ արագ տեսակավորման լավագույն հաշվողական դժվարությունը Θ(nlgn) է, իսկ վատագույնը՝ Θ(n2)։ Այս աղյուսակը ցույց է տալիս մեր սովորած չորս տեսակավորման ալգորիթմները և դրանց հաշվողական դժվարությունները․
ԱլգորիթմՎատագույն հաշվողական դժվարությունԼավագույն հաշվողական դժվարությունՄիջին հաշվողական դժվարություն
Ընտրանքային տեսակավորումΘ(n2)Θ(n2)Θ(n2)
Մուտքային տեսակավորումΘ(n2)Θ(n)Θ(n2)
Միաձուլման տեսակավորումΘ(nlgn)Θ(nlgn)Θ(nlgn)
Արագ տեսակավորումΘ(n2)Θ(nlgn)Θ(nlgn)

Բաժանիր և տիրիր

Միաձուլման տեսակավորումն ու արագ տեսակավորումն ունեն ռեկուրսիայի հիման վրա ստեղծված ալգորիթմական ստրատեգիա։ Այս ստրատեգիան՝ Բաժանիր և տիրիր, բաժանում է խնդիրը ենթախնդիրների, որոնք նման են դրան, ռեկուրսիվորեն լուծում է ենթախնդիրները և վերջապես միավորում է դրանք, որպեսզի դրանց օգնությամբ լուծի իրական խնդիրը։ Քանի որ «Բաժանիր և տիրիր» ռազմավարությունը ռեկուրսիվորեն է լուծում ենթախնդիրները, բոլոր ենթախնդիրները պետք է ավելի փոքր լինեն, քան խնդիրը, և ենթախնդիրների համար պետք է լինի առաջին քայլ։ Կարող ենք ասել, որ «Բաժանիր և տիրիր» ալգորիթմը երեք մաս ունի․
  1. Բաժանել խնդիրն ինչ-որ քանակի ենթախնդիրների, որոնք խնդրի փոքր մասն են կազմում։
  2. Տիրել ենթախնդիրներին՝ դրանք ռեկուրսիվորեն լուծելով։ Եթե դրանք բավականաչափ փոքր են, կարող ես լուծել որպես առաջին քայլ։
  3. Միավորել ենթախնդիրների լուծումներն իրական խնդրին։
Դու հեշտությամբ կարող ես հիշել «Բաժանիր և տիրիր» ալգորիթմի քայլերը՝ որպես բաժանել, տիրել, միավորել։ Ահա թե ինչպես պատկերացնել այն՝ համարելով, որ մի բաժանումը ստեղծում է երկու ենթախնդիր (չնայած «Բաժանիր և տիրիր» ռազմավարության որոշ ալգորիթմներ ստեղծում են ավելին, քան երկուսը)․
Եթե այն ընդլայնենք ևս երկու ռեկուրենտ քայլերի, այսպիսի տեսքի կգա․
Քանի որ «Բաժանիր և տիրիր» ռազմավարությունը ստեղծում է առնվազն երկու ենթախնդիր, «Բաժանիր և տիրիր» ալգորիթմը կատարում է մի քանի ռեկուրենտ կանչ։
Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։

Ուզո՞ւմ ես միանալ խոսակցությանը։

Առայժմ հրապարակումներ չկան։
Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում: