1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar

Qattiq va kuchsiz polinom vaqti

Ba'zi kontekstlarda, ayniqsa optimallashtirishda, algoritmlar bilan ajralib turadi qat'iy polinom vaqti va zaif polinom vaqti... Bu ikki tushuncha faqat butun sonlardan tashkil topgan kiritish uchun amal qiladi.

Arifmetik hisoblash modelida qat'iy polinom vaqti aniqlanadi. Bu modelda operandlar uzunligidan qat’iy nazar, bajarilish birliklari sifatida asosiy arifmetik amallar (qo‘shish, ayirish, ko‘paytirish, bo‘lish va taqqoslash) olinadi. Algoritm qat'iy polinom vaqtida ishlaydi, agar

1. 
   arifmetik hisoblash modelidagi operatsiyalar soni kirish oqimidagi butun sonlar sonidagi polinom bilan cheklangan va
   
2. 
   algoritm tomonidan qo'llaniladigan xotira kirish o'lchamidagi polinom bilan chegaralanadi.
   

Bu ikki xususiyatga ega bo‘lgan har qanday algoritmni Tyuring mashinasida arifmetik amallarni bajarish uchun tegishli algoritmlar bilan arifmetik amallarni almashtirish orqali ko‘p nomli vaqt algoritmiga keltirish mumkin. Yuqoridagi talablarning ikkinchisi bajarilmasa, bu endi to'g'ri bo'lmaydi. Butun son (Tyuring mashinasida n ga proportsional xotirani egallaydi) berilgan bo‘lsa, uni takroriy darajaga ko‘tarish yordamida n ta amalda hisoblash mumkin. Biroq, xotira ifodalash uchun ishlatiladi 2 2 n (\ displaystyle 2 ^ (2 ^ (n))), ga mutanosib 2 n (\ displaystyle 2 ^ (n)), va u kirish uchun ishlatiladigan xotiraga polinom emas, balki eksponensial jihatdan bog'liq. Demak, Tyuring mashinasida bu hisoblarni ko'pnomli vaqtda bajarish mumkin emas, lekin ko'p nomli arifmetik amallarni bajarish mumkin.

Aksincha, Tyuring mashinasining qadamlar sonida ishlaydigan, ikkilik kodli kiritishning polinom uzunligi bilan chegaralangan, lekin arifmetik amallar sonida ishlamaydigan, sonlar sonidagi polinom bilan cheklangan algoritmlar mavjud. kiritish. Bunga Evklidning ikkita butun sonning eng katta umumiy boʻluvchisini hisoblash algoritmi misol boʻla oladi. Ikkita butun son uchun a (\ displaystyle a) va b (\ displey uslubi b) algoritmning ishlash muddati cheklangan O ((log ⁡ a + log ⁡ b) 2) (\ displaystyle O ((\ log \ a + \ log \ b) ^ (2))) Tyuring mashinasining qadamlari. Bu raqam sonlarning ikkilik ko'rinishining o'lchamining polinomidir a (\ displaystyle a) va b (\ displey uslubi b), taxminan sifatida ifodalanishi mumkin log ⁡ a + log ⁡ b (\ displaystyle \ log \ a + \ log \ b)... Shu bilan birga, arifmetik amallar sonini kiritishdagi butun sonlar soni bilan cheklab bo'lmaydi (bu holda bu doimiy hisoblanadi - kiritishda faqat ikkita raqam mavjud). Ushbu eslatmani hisobga olgan holda, algoritm qat'iy polinom vaqtida ishlamaydi. Algoritmning haqiqiy ishlash vaqti qiymatlarga bog'liq a (\ displaystyle a) va b (\ displey uslubi b), faqat kirishdagi butun sonlar soni emas.

Agar algoritm polinom vaqtida ishlasa, lekin qat'iy polinom vaqtida emas, deyiladi. zaif polinom vaqti... Kuchsiz ko'phadli algoritmi ma'lum bo'lgan, lekin qat'iy ko'phadli algoritmi noma'lum bo'lgan masalaning taniqli misoli chiziqli dasturlashdir. Zaif polinom vaqtini psevdo polinom vaqti bilan aralashtirib yubormaslik kerak.