Kamaytirish polinom vaqtimi?

2024 Muallif: Fiona Howard | [email protected]. Oxirgi o'zgartirilgan: 2024-01-10 06:44

Hisoblash murakkabligi nazariyasida polinom-vaqtni qisqartirish bir masalani boshqayordamida hal qilish usulidir. Ko'p nomli vaqtni qisqartirish murakkablik nazariyasida murakkablik sinflarini va bu sinflar uchun to'liq muammolarni aniqlash uchun tez-tez ishlatiladi. …

Koʻpnomli vaqt nima hisoblanadi?

Algoritmning ishlash vaqti algoritm uchun kiritilgan oʻlchamdagi polinom ifodasi bilan yuqori chegaralangan boʻlsa, yaʼni T(n)=O(n^k) baʼzi musbat doimiy k.

Biror narsa polinom vaqt ekanligini qanday bilasiz?

3 Javoblar. Agar ba'zi bir k uchun C>0, n o'lchamdagi kirishlar bo'yicha uning ishlash vaqti ko'pi bilan Cnk bo'lsa, algoritm ko'pnomli (polinomli ishlash vaqtiga ega). Ekvivalent tarzda, algoritm ko'pnomli hisoblanadi, agar ba'zi k>0 uchun uning n o'lchamdagi kirishlarda ishlash vaqti O(nk).

Eksponensial vaqt ichida qisqarishga ruxsat berilsa nima bo'ladi?

Agar qisqarishga eksponensial vaqt ruxsat etilsa, u asl muammoni toʻliq hal qilishi va maqsadli muammoning arzimas misolini yaratishi mumkin Bu NPdagi har bir muammoni har bir muammoga qisqartirish mumkinligini bildiradi. Bunday qisqartirishlar bo'yicha boshqa muammo, shuning uchun NPdagi har bir muammo eksponensial vaqtni qisqartirish uchun NP-to'liqdir.

Eksponensial algoritm nima?

Algoritm eksponensial vaqt deyiladi, agar T(n) 2^{poly(bilan yuqori chegaralangan bo'lsa) )} , bu erda poli(n) n dagi ba'zi polinomdir. Rasmiyroq qilib aytganda, algoritm koʻrsatkichli vaqt hisoblanadi, agar T(n) baʼzi doimiy k uchun O(2^{nk) bilan chegaralangan boʻlsa. Ref:Wiki.}