Рандомизирленген және рекурсивті алгоритм
Рандомизацияланған алгоритмдер алгоритмді орындау кезінде кездейсоқ таңдау жасау арқылы логикасына кездейсоқтық сезімін қосады. Осы кездейсоқтыққа байланысты алгоритм әрекеті тіпті тіркелген кіріс үшін де өзгеруі мүмкін. Көптеген мәселелер үшін рандомизацияланған алгоритмдер ең қарапайым және тиімді шешімдерді ұсынады. Рекурсивті алгоритмдер мәселенің шешімін сол мәселенің кішірек ішкі есептерінің шешімдерін табу арқылы табуға болады деген идеяға негізделген. Рекурсия информатикадағы мәселелердің шешімін табу үшін кеңінен қолданылады және көптеген жоғары деңгейлі бағдарламалау тілдері рекурсияны қолдайды.
Рандомизацияланған алгоритм дегеніміз не?
Рандомизацияланған алгоритмдер алгоритмнің орындалуын бағыттайтын кездейсоқ таңдаулар жасау арқылы кездейсоқтық сезімін біріктіреді. Бұл әдетте қосымша кіріс ретінде жалған кездейсоқ сандар генераторымен жасалған кездейсоқ сандар жиынын алу арқылы жасалады. Осыған байланысты алгоритм әрекеті тіпті тіркелген кіріс үшін де өзгеруі мүмкін. Quicksort – кең танымал алгоритм, ол кездейсоқтық тұжырымдамасын қолданады және кіріс қасиеттеріне қарамастан оның жұмыс уақыты O(n log n) болады. Әрі қарай, есептеу геометриясында дөңес корпус сияқты құрылыс құрылымдары үшін рандомизацияланған қосымша құрылыс әдісі қолданылады. Бұл әдісте енгізу нүктелері кездейсоқ ауыстырылады, содан кейін құрылымға бір-бірден енгізіледі. Рандомизацияланған алгоритмді енгізу бір мәселе үшін детерминирленген алгоритмді жүзеге асыруға қарағанда салыстырмалы түрде қарапайым. Рандомизацияланған алгоритмді жобалаудағы ең үлкен қиындық уақыт пен кеңістіктің күрделілігіне асимптотикалық талдауды орындауда жатыр.
Рекурсивті алгоритм дегеніміз не?
Рекурсивті алгоритмдер мәселенің шешімін бір есептің кішірек ішкі есептерінің шешімдерін табу арқылы табуға болады деген идеяға негізделген. Рекурсивті алгоритмде функция өзінің бұрынғы нұсқасы бойынша анықталады. Мәңгі сілтеме жасамау үшін бұл өзіндік сілтемеде тоқтату шарты болуы керек екенін ескеру маңызды. Аяқтау шарты өзіне сілтеме жасамас бұрын тексеріледі. Рекурсивті алгоритмнің бастапқы қадамы мәселенің рекурсивті анықтамасының базистік сөйлемімен байланысты. Бастапқы қадамнан кейінгі қадамдар есептің индуктивті сөйлемдерімен байланысты. Рекурсивті алгоритмдер көптеген жағдайларда қарапайым шешімді қамтамасыз етеді және сол мәселенің итеративті алгоритміне қарағанда табиғи ойлау тәсіліне жақынырақ. Бірақ жалпы алғанда, рекурсивті алгоритмдер көбірек жадты қажет етеді және олар есептеу жағынан қымбат.
Рандомизацияланған және рекурсивті алгоритмнің айырмашылығы неде?
Кездейсоқ алгоритмдер алгоритмнің орындалуына әсер етуі мүмкін кездейсоқ таңдаулар жасау арқылы кездейсоқтық сезімін қолданатын алгоритмдер, ал рекурсивті алгоритмдер есептің шешімін табу арқылы табуға болады деген идеяға негізделген алгоритмдер. бірдей мәселенің кішігірім қосалқы мәселелерінің шешімдері. Кездейсоқ алгоритмдердегі кездейсоқтыққа байланысты алгоритмнің әрекеті тіпті бір енгізу үшін де өзгеруі мүмкін (алгоритмнің әртүрлі орындалуында). Бірақ бұл рекурсивті алгоритмдерде мүмкін емес және рекурсивті алгоритмнің әрекеті тіркелген кіріс үшін бірдей болады.
