Պատահական ընդդեմ ռեկուրսիվ ալգորիթմի
Պատահականացված ալգորիթմներն իրենց տրամաբանության մեջ ներառում են պատահականության զգացողություն՝ ալգորիթմի կատարման ընթացքում պատահական ընտրություն կատարելով: Այս պատահականության պատճառով ալգորիթմի վարքագիծը կարող է փոխվել նույնիսկ ֆիքսված մուտքագրման դեպքում: Շատ խնդիրների դեպքում պատահականացված ալգորիթմները տալիս են ամենապարզ և արդյունավետ լուծումները: Ռեկուրսիվ ալգորիթմները հիմնված են այն գաղափարի վրա, որ խնդրի լուծումը կարելի է գտնել նույն խնդրի փոքր ենթախնդիրների լուծումներ գտնելու միջոցով: Recursion-ը լայնորեն օգտագործվում է համակարգչային գիտության խնդիրների լուծումներ գտնելու համար, և շատ բարձր մակարդակի ծրագրավորման լեզուներ աջակցում են ռեկուրսիային:
Ի՞նչ է պատահականացված ալգորիթմը:
Պատահականացված ալգորիթմները ներառում են պատահականության զգացողություն՝ կատարելով պատահական ընտրություններ, որոնք առաջնորդում են ալգորիթմի կատարումը: Սա սովորաբար արվում է՝ որպես լրացուցիչ մուտքագրում ընդունելով կեղծ պատահական թվերի գեներատորի կողմից գեներացված մի շարք պատահական թվեր: Դրա շնորհիվ ալգորիթմի վարքագիծը կարող է փոխվել նույնիսկ ֆիքսված մուտքագրման դեպքում: Quicksort-ը լայնորեն հայտնի ալգորիթմ է, որն օգտագործում է պատահականության հայեցակարգը և ունի O(n log n) գործարկման ժամանակ՝ անկախ մուտքային հատկություններից: Ավելին, պատահականացված աստիճանական կառուցման մեթոդը օգտագործվում է հաշվարկային երկրաչափության մեջ ուռուցիկ կորպուսի նման կառուցվածքներ կառուցելու համար: Այս մեթոդով մուտքային կետերը պատահականորեն փոխվում են, այնուհետև մեկ առ մեկ տեղադրվում են կառուցվածքում: Պատահականացված ալգորիթմի իրականացումը համեմատաբար պարզ է, քան նույն խնդրի համար դետերմինիստական ալգորիթմի կիրառումը: Պատահականացված ալգորիթմի նախագծման ամենամեծ մարտահրավերը ժամանակի և տարածության բարդության համար ասիմպտոտիկ վերլուծություն կատարելն է:
Ի՞նչ է ռեկուրսիվ ալգորիթմը:
Ռեկուրսիվ ալգորիթմները հիմնված են այն գաղափարի վրա, որ խնդրի լուծումը կարելի է գտնել նույն խնդրի փոքր ենթախնդիրների լուծումներ գտնելու միջոցով: Ռեկուրսիվ ալգորիթմում ֆունկցիան սահմանվում է իր ավելի վաղ տարբերակի տեսանկյունից: Կարևոր է նշել, որ այս ինքնահղումը պետք է ունենա դադարեցման պայման՝ ընդմիշտ ինքն իրեն հղում անելուց խուսափելու համար: Դադարեցման պայմանը ստուգվում է նախքան ինքնին հղում կատարելը: Ռեկուրսիվ ալգորիթմի սկզբնական քայլը կապված է խնդրի ռեկուրսիվ սահմանման հիմնական դրույթի հետ։ Սկզբնական քայլին հաջորդող քայլերը կապված են խնդրի ինդուկտիվ դրույթների հետ։ Ռեկուրսիվ ալգորիթմները շատ իրավիճակներում ավելի պարզ լուծում են տալիս, և այն ավելի մոտ է բնական մտածելակերպին, քան նույն խնդրի կրկնվող ալգորիթմը: Բայց ընդհանուր առմամբ, ռեկուրսիվ ալգորիթմները պահանջում են ավելի շատ հիշողություն և դրանք հաշվողականորեն թանկ են:
Ո՞րն է տարբերությունը պատահականացված և ռեկուրսիվ ալգորիթմի միջև:
Պատահական ալգորիթմներն այն ալգորիթմներն են, որոնք օգտագործում են պատահականության զգացողություն՝ կատարելով պատահական ընտրություններ, որոնք կարող են ազդել ալգորիթմի կատարման վրա, մինչդեռ ռեկուրսիվ ալգորիթմներն ալգորիթմներ են, որոնք հիմնված են այն գաղափարի վրա, որ խնդրի լուծումը կարելի է գտնել գտնելով։ նույն խնդրի փոքր ենթախնդիրների լուծումները: Պատահական ալգորիթմների պատահականության պատճառով ալգորիթմի վարքագիծը կարող է փոխվել նույնիսկ նույն մուտքագրման դեպքում (ալգորիթմի տարբեր կատարումներում): Բայց դա հնարավոր չէ ռեկուրսիվ ալգորիթմներում, և ռեկուրսիվ ալգորիթմի վարքագիծը նույնը կլինի ֆիքսված մուտքագրման համար:
