Тооцооллын нарийн төвөгтэй байдлын онолд олон гишүүнт цагийн бууралт нь нэг асуудлыг нөгөө ашиглан шийдвэрлэх арга юм. Олон гишүүнт цагийн бууруулалтыг нарийн төвөгтэй байдлын онолд ихэвчлэн нарийн төвөгтэй байдлын анги ба тэдгээр ангиллын бүрэн бодлогуудыг тодорхойлоход ашигладаг. …
Олон гишүүнт цаг гэж юу вэ?
Алгоритмын ажиллах хугацаа нь алгоритмын оролтын хэмжээн дэх олон гишүүнт илэрхийллээр дээд хязгаарлагдсан, өөрөөр хэлбэл, T(n)=O(бол алгоритмыг олон гишүүнт хугацаатай гэж хэлнэ. nk) зарим эерэг тогтмол k.
Ямар нэг зүйл олон гишүүнт цаг мөн эсэхийг та яаж мэдэх вэ?
3 Хариултууд. Зарим k, C>0-ийн хувьд n хэмжээтэй оролт дээр ажиллах хугацаа нь хамгийн ихдээ Cnk байвал алгоритм нь олон гишүүнт (олон гишүүн ажиллах хугацаатай) болно. Зарим k>0-ийн хувьд n хэмжээтэй оролт дээр ажиллах хугацаа нь O(nk) байвал алгоритм нь олон гишүүнт болно.
Экспоненциал хугацаанд багасгахыг зөвшөөрвөл яах вэ?
Хэрэв багасгахыг зөвшөөрвөл экспоненциал хугацаатай бол энэ нь анхны асуудлыг бүрэн шийдэж, зорилтот асуудлын өчүүхэн жишээг гаргаж чадна Энэ нь NP-н бүх асуудал бүрд буурдаг гэсэн үг юм. Ийм төрлийн бууралттай бусад асуудал тул NP дахь бодлого бүр экспоненциал хугацааг багасгахад зориулагдсан NP-д бүрэн гүйцэд байна.
Экспоненциал алгоритм гэж юу вэ?
Алгоритмыг экспоненциал хугацаа гэнэ, хэрэв T(n) нь 2poly(-ээр дээд хязгаарлагдсан бол ) , энд poly(n) нь n дахь олон гишүүнт юм. Илүү албан ёсоор, хэрэв T(n) нь тогтмол k-д O(2nk)-ээр хязгаарлагддаг бол алгоритм нь экспоненциал хугацаа болно. Ref:Wiki.
