Тооцооллын нарийн төвөгтэй байдлын онол нь тооцооллын асуудлыг нөөцийн ашиглалтаар нь ангилж, эдгээр ангиудыг хооронд нь холбоход чиглэдэг. Тооцооллын асуудал нь компьютерээр шийдэгддэг даалгавар юм. Тооцооллын асуудлыг алгоритм гэх мэт математикийн алхмуудыг механик аргаар шийдэж болно.
Та алгоритмын нарийн төвөгтэй байдал гэж юу гэсэн үг вэ?
Алгоритмын нийлмэл байдал нь өгөгдсөн хэмжээтэй (n) оролтод алгоритмд шаардагдах хугацаа ба/эсвэл орон зайн хэмжүүр юм.
Өгөгдлийн бүтэц дэх алгоритмын нарийн төвөгтэй байдал гэж юу вэ?
Алгоритмийн нарийн төвөгтэй байдал нь хэмжээний n өгөгдсөн оролтыг алгоритм хэр удаан хийж дуусгахыг илэрхийлдэг хэмжүүр юм. Хэрэв алгоритм нь масштабтай байх ёстой бол үр дүнг n-ийн том утгын хувьд хязгаарлагдмал, практик хугацааны дотор тооцоолох ёстой. Ийм учраас n нь хязгааргүйд ойртох тусам нарийн төвөгтэй байдлыг асимптотоор тооцдог.
Алгоритмийн нарийн төвөгтэй байдал яагаад чухал вэ?
Компьютерийн эрдэмтэд код бичихээсээ өмнө алгоритм хэр хурдан ажиллах, түүнд хэр их санах ой шаардагдахыг урьдчилан таамаглах боломжийг олгодог математикийн нарийн төвөгтэй хэмжүүрүүдийг ашигладаг. Ийм таамаглал нь программистуудад бодит хэрэглээний алгоритмуудыг хэрэгжүүлэх, сонгоход чухал гарын авлага болдог.
Алгоритмийн нарийн төвөгтэй байдлыг хэрхэн тооцдог вэ?
Аливаа давталтын хувьд бид тэдгээрийн доторх блокийн ажиллах хугацааг олж мэдээд программын тоогоор үржүүлнэгогцоо давтана. Оролтын хэмжээтэй пропорциональ ургадаг бүх гогцоонууд нь шугаман хугацааны нарийн төвөгтэй O(n). Хэрэв та массивын зөвхөн хагасыг нь давтвал энэ нь O(n) хэвээр байна.
