Tasodifiy va rekursiv algoritm
Tasodifiy algoritmlar algoritmni bajarish jarayonida tasodifiy tanlovlar qilish orqali oʻz mantigʻida tasodifiylik hissini oʻz ichiga oladi. Ushbu tasodifiylik tufayli algoritmning xatti-harakati hatto sobit kirish uchun ham o'zgarishi mumkin. Ko'pgina muammolar uchun tasodifiy algoritmlar eng oddiy va samarali echimlarni taqdim etadi. Rekursiv algoritmlar muammoning yechimini bir xil muammoning kichikroq kichik muammolariga yechim topish orqali topish mumkin degan fikrga asoslanadi. Rekursiya informatikadagi muammolar yechimini topish uchun keng qo'llaniladi va ko'plab yuqori darajadagi dasturlash tillari rekursiyani qo'llab-quvvatlaydi.
Tasodifiy algoritm nima?
Tasodifiy algoritmlar algoritmning bajarilishini boshqaradigan tasodifiy tanlovlar qilish orqali tasodifiylik hissini o'z ichiga oladi. Bu odatda qo'shimcha kirish sifatida psevdor tasodifiy sonlar generatori tomonidan yaratilgan tasodifiy sonlar to'plamini olish orqali amalga oshiriladi. Shu sababli, algoritmning xatti-harakati hatto qattiq kirish uchun ham o'zgarishi mumkin. Quicksort - bu tasodifiylik kontseptsiyasidan foydalanadigan keng tarqalgan algoritm bo'lib, kirish xususiyatlaridan qat'i nazar, O(n log n) ish vaqtiga ega. Bundan tashqari, hisoblash geometriyasida konveks korpus kabi tuzilmalarni qurish uchun tasodifiy qo'shimcha qurilish usuli qo'llaniladi. Ushbu usulda kirish nuqtalari tasodifiy almashtiriladi va keyin strukturaga birma-bir kiritiladi. Tasodifiy algoritmni amalga oshirish bir xil muammo uchun deterministik algoritmni amalga oshirishdan ko'ra nisbatan sodda. Tasodifiy algoritmni loyihalashda eng katta qiyinchilik vaqt va makon murakkabligi uchun asimptotik tahlilni amalga oshirishda yotadi.
Rekursiv algoritm nima?
Rekursiv algoritmlar muammoning yechimini bir xil muammoning kichikroq kichik muammolariga yechim topish orqali topish mumkin degan fikrga asoslanadi. Rekursiv algoritmda funktsiya o'zining oldingi versiyasi nuqtai nazaridan aniqlanadi. Shuni ta'kidlash kerakki, bu o'z-o'zidan havola o'zini abadiy ishlatmaslik uchun tugatish shartiga ega bo'lishi kerak. Tugatish sharti o'ziga havola qilishdan oldin tekshiriladi. Rekursiv algoritmning dastlabki bosqichi muammoning rekursiv ta'rifining bazis bandi bilan bog'liq. Dastlabki bosqichdan keyingi bosqichlar muammoning induktiv bandlari bilan bog'liq. Rekursiv algoritmlar ko'p vaziyatlarda oddiyroq yechimni ta'minlaydi va u xuddi shu muammo uchun iterativ algoritmga qaraganda tabiiy fikrlash usuliga yaqinroqdir. Ammo umuman olganda, rekursiv algoritmlar koʻproq xotira talab qiladi va ular hisoblash jihatidan qimmat.
Tasodifiy va rekursiv algoritm oʻrtasidagi farq nima?
Tasodifiy algoritmlar algoritmning bajarilishiga ta'sir qilishi mumkin bo'lgan tasodifiy tanlovlar qilish orqali tasodifiylik hissidan foydalanadigan algoritmlar, rekursiv algoritmlar esa muammoning yechimini topish orqali topish mumkin degan fikrga asoslangan algoritmlardir. bir xil muammoning kichik kichik muammolarini hal qilish. Tasodifiy algoritmlarning tasodifiyligi tufayli algoritmning xatti-harakati hatto bir xil kiritish uchun ham o'zgarishi mumkin (algoritmning turli xil bajarilishida). Lekin bu rekursiv algoritmlarda mumkin emas va rekursiv algoritmning harakati sobit kirish uchun bir xil bo'ladi.
