Рандомизацияланган жана Рекурсивдүү Алгоритм
Рандомизацияланган алгоритмдер алгоритмди аткаруу учурунда туш келди тандоолорду жасоо менен логикасына кокустук сезимин камтыйт. Бул кокустуктан улам, алгоритмдин жүрүм-туруму туруктуу киргизүү үчүн да өзгөрүшү мүмкүн. Көптөгөн көйгөйлөр үчүн рандомизацияланган алгоритмдер эң жөнөкөй жана эффективдүү чечимдерди берет. Рекурсивдүү алгоритмдер маселенин чечилишин ошол эле маселенин кичирээк проблемаларынын чечимдерин табуу аркылуу табууга болот деген ойго негизделген. Рекурсия информатикадагы көйгөйлөрдүн чечимдерин табуу үчүн кеңири колдонулат жана көптөгөн жогорку деңгээлдеги программалоо тилдери рекурсияны колдойт.
Рандомизацияланган алгоритм деген эмне?
Рандомизацияланган алгоритмдер алгоритмдин аткарылышын жетектөөчү туш келди тандоолорду жасоо менен кокустук сезимин камтыйт. Бул, адатта, кошумча киргизүү катары псевдордук сандардын генератору тарабынан түзүлгөн кокустук сандардын топтомун алуу менен ишке ашырылат. Ушундан улам, алгоритмдин жүрүм-туруму туруктуу киргизүү үчүн да өзгөрүшү мүмкүн. Quicksort кокустук түшүнүгүн колдонгон кеңири белгилүү алгоритм жана киргизүү касиеттерине карабастан анын иштөө убактысы O(n log n) болот. Андан тышкары, эсептөө геометриясында томпок корпус сыяктуу конструкцияларды куруу үчүн рандомизацияланган кошумча курулуш ыкмасы колдонулат. Бул ыкмада киргизүү чекиттери туш келди алмаштырылып, анан структурага бирден киргизилет. Рандомизацияланган алгоритмди ишке ашыруу бир эле маселе үчүн детерминисттик алгоритмди ишке ашырууга караганда салыштырмалуу жөнөкөй. Рандомизацияланган алгоритмди иштеп чыгуудагы эң чоң кыйынчылык убакыт жана мейкиндик татаалдыгы үчүн асимптотикалык анализ жүргүзүүдө.
Рекурсивдүү Алгоритм деген эмне?
Рекурсивдүү алгоритмдер маселенин чечилишин ошол эле маселенин кичирээк чакан көйгөйлөрүнүн чечимдерин табуу аркылуу табууга болот деген ойго негизделген. Рекурсивдүү алгоритмде функция өзүнүн мурунку версиясы боюнча аныкталат. Бул өзүн-өзү шилтеме биротоло өзүнө шилтемени болтурбоо үчүн токтотуу шарты болушу керек экенин белгилей кетүү маанилүү. Аяктоо шарты өзүнө шилтеме жасоодон мурун текшерилет. Рекурсивдүү алгоритмдин баштапкы кадамы маселенин рекурсивдүү аныктамасынын базис пункту менен байланышкан. Баштапкы кадамдан кийинки кадамдар маселенин индуктивдүү сүйлөмдөрү менен байланышкан. Рекурсивдүү алгоритмдер көп жагдайларда жөнөкөй чечимди камсыздайт жана бир эле маселенин кайталануучу алгоритмине караганда табигый ой жүгүртүү ыкмасына жакыныраак. Бирок жалпысынан рекурсивдүү алгоритмдер көбүрөөк эстутумду талап кылат жана алар эсептөө жагынан кымбат.
Рандомизацияланган алгоритм менен рекурсивдүү алгоритмдин ортосунда кандай айырма бар?
Кокустук алгоритмдер алгоритмдин аткарылышына таасирин тийгизе турган кокустуктарды кабыл алуу менен кокустук сезимин колдонгон алгоритмдер, ал эми рекурсивдүү алгоритмдер маселенин чечүү жолун табуу аркылуу табууга болот деген ойго негизделген алгоритмдер. бир эле маселенин кичинекей чакан проблемаларын чечүү. Кокус алгоритмдердеги кокустуктан улам, алгоритмдин жүрүм-туруму бир эле киргизүү үчүн да өзгөрүшү мүмкүн (алгоритмдин ар кандай аткарылышында). Бирок бул рекурсивдүү алгоритмдерде мүмкүн эмес жана рекурсивдүү алгоритмдин жүрүм-туруму белгиленген киргизүү үчүн бирдей болот.
