Բաժանիր և տիրիր
«Բաժանիր և տիրիր» (Divide and Conquer) ալգորիթմական խնդիրներ լուծելու լայնորեն կիրառվող մոտեցում է։ Մենք արդեն տեսել ենք որոշ մեթոդներ ալգորիթմներ լուծելու համար. օրինակ, Ագահ Ալգորիթմները (Greedy Algorithms) յուրաքանչյուր քայլում ընտրում են ամենաօպտիմալ լուծումը, իսկ Դինամիկ Ծրագրավորումը (Dynamic Programming) ստեղծում է ընթացիկ վիճակը նախորդ վիճակների հիման վրա։ Իսկ «Բաժանիր և տիրիր» մեթոդի դեպքում մենք խնդիրը բաժանում ենք ավելի փոքր ենթախնդիրների և լուծում դրանք հերթով, այնուհետև համադրում ենք արդյունքները, որպեսզի լուծենք նախնական խնդիրը։ Այսինքն, մենք բաժանում ենք խնդիրը ենթախնդիրների և տիրում ենք ամբողջ խնդրին, երբ համադրում ենք այդ ենթախնդիրների արդյունքները։
Առաջադրանք
Պատկերացրեք, որ ձեզ տրված է 512 թիվ, և կա 512 հատ հատուկ (շատ փոքր ու մասնագիտացված) համակարգիչ, որոնք կարող են ստանալ երկու թիվ և վերադարձնել դրանցից մեծագույնը։
Ցանկանում եք գտնել տրված 512 թվերից մեծագույնը հնարավորինս արագ։
Յուրաքանչյուր մասնագիտացված համակարգիչ ենթադրում է, որ երկու թիվ ստանալիս, մեկ վայրկյանում վերադարձնում է մեծագույնը (այո՛, դրանք բավականին դանդաղ են 🐌)։ Կարո՞ղ եք մտածել այնպիսի ալգորիթմ, որը թույլ կտա ամենասեղմ ժամանակում որոշել բոլոր թվերից մեծագույնը։