Санамсаргүй ба рекурсив алгоритм
Санамсаргүй алгоритмууд нь алгоритмыг гүйцэтгэх явцад санамсаргүй сонголт хийх замаар логикдоо санамсаргүй байдлын мэдрэмжийг шингээдэг. Энэхүү санамсаргүй байдлаас шалтгаалан алгоритмын үйлдэл нь тогтмол оролтод хүртэл өөрчлөгдөж болно. Олон асуудлын хувьд санамсаргүй алгоритмууд нь хамгийн энгийн бөгөөд үр дүнтэй шийдлүүдийг өгдөг. Рекурсив алгоритмууд нь ижил асуудлын жижиг дэд асуудлуудын шийдлийг олох замаар асуудлын шийдлийг олох боломжтой гэсэн санаан дээр суурилдаг. Рекурсийг компьютерийн шинжлэх ухааны асуудлын шийдлийг олоход өргөнөөр ашигладаг бөгөөд өндөр түвшний програмчлалын олон хэл нь рекурсийг дэмждэг.
Санамсаргүй алгоритм гэж юу вэ?
Санамсаргүй алгоритмууд нь алгоритмын гүйцэтгэлийг удирдан чиглүүлдэг санамсаргүй сонголт хийх замаар санамсаргүй байдлын мэдрэмжийг агуулдаг. Энэ нь ихэвчлэн псевдор санамсаргүй тоо үүсгэгчийн үүсгэсэн санамсаргүй тооны багцыг нэмэлт оролт болгон авах замаар хийгддэг. Үүнээс үүдэн алгоритмын үйлдэл нь тогтмол оролтод хүртэл өөрчлөгдөж болно. Quicksort нь санамсаргүй байдлын тухай ойлголтыг ашигладаг алдартай алгоритм бөгөөд оролтын шинж чанараас үл хамааран O(n log n) ажиллах хугацаатай байдаг. Цаашилбал, тооцооллын геометрийн гүдгэр их бие гэх мэт барилга байгууламж барихад санамсаргүй байдлаар нэмэгдүүлсэн барилгын аргыг ашигладаг. Энэ аргын хувьд оролтын цэгүүдийг санамсаргүй байдлаар сольж, дараа нь бүтцэд нэг нэгээр нь оруулдаг. Санамсаргүй алгоритмыг хэрэгжүүлэх нь ижил асуудалд детерминистик алгоритмыг хэрэгжүүлэхээс харьцангуй хялбар юм. Санамсаргүй алгоритмыг боловсруулахад тулгардаг хамгийн том бэрхшээл бол цаг хугацаа, орон зайн нарийн төвөгтэй байдлын асимптотик шинжилгээ хийх явдал юм.
Рекурсив алгоритм гэж юу вэ?
Рекурсив алгоритмууд нь ижил асуудлын жижиг дэд асуудлын шийдлүүдийг олох замаар асуудлын шийдлийг олох боломжтой гэсэн санаан дээр суурилдаг. Рекурсив алгоритмд функцийг өөрийн өмнөх хувилбараар тодорхойлдог. Энэ өөрөө лавлагаа нь үүрд лавлахаас зайлсхийхийн тулд дуусгавар болох нөхцөлтэй байх ёстой гэдгийг анхаарах нь чухал юм. Өөрийгөө лавлахын өмнө дуусгавар болох нөхцөлийг шалгана. Рекурсив алгоритмын эхний алхам нь асуудлын рекурсив тодорхойлолтын үндсэн заалттай холбоотой байдаг. Эхний алхамыг дагаж мөрдөх алхмууд нь асуудлын индуктив заалтуудтай холбоотой байдаг. Рекурсив алгоритм нь олон нөхцөл байдалд илүү хялбар шийдлийг өгдөг бөгөөд энэ нь ижил асуудлын давталтын алгоритмаас илүү байгалийн сэтгэлгээнд ойр байдаг. Гэхдээ ерөнхийдөө рекурсив алгоритмууд илүү их санах ой шаарддаг бөгөөд тооцооллын хувьд үнэтэй байдаг.
Санамсаргүй болон рекурсив алгоритм хоёрын ялгаа нь юу вэ?
Санамсаргүй алгоритмууд нь алгоритмын гүйцэтгэлд нөлөөлж болох санамсаргүй сонголт хийх замаар санамсаргүй байдлын мэдрэмжийг ашигладаг алгоритмууд бол рекурсив алгоритмууд нь асуудлын шийдлийг олох замаар олж болно гэсэн санаан дээр үндэслэсэн алгоритмууд юм. ижил асуудлын жижиг дэд асуудлуудын шийдэл. Санамсаргүй алгоритмуудын санамсаргүй байдлаас шалтгаалан алгоритмын үйлдэл нь ижил оролтод ч өөрчлөгдөж болно (алгоритмын өөр өөр гүйцэтгэлд). Гэхдээ энэ нь рекурсив алгоритмд боломжгүй бөгөөд рекурсив алгоритмын үйлдэл тогтмол оролттой адил байх болно.
