Mavzu: Algoritm murakabligini statik va dinamik o’lchovlari. Vaqt va xotira xajmi bo’yicha qiyinchiliklar

Chiziqli logarifmik vaqt
Chiziqli-logarifmik - bu ko'rsatkichli kvazizikli vaqtning maxsus holati k= 1 logarifmik hadda.
Chiziqli logarifmik funktsiya shaklning funktsiyasidir n jurnal n(masalan, mahsulot chiziqli va logarifmik atamalar). Algoritm ishlashi aytiladi chiziqli-logarifmik vaqt, agar T(n) = O ( n jurnal n) ... Shunday qilib, chiziqli-logarifmik element chiziqli haddan tezroq, lekin har qanday polinomga qaraganda sekinroq o'sadi. n 1 dan qat'iy yuqori darajaga ega.
Ko'p hollarda ish vaqti n jurnal n oddiygina operatsiya natijasidir t (log n) n bir marta. Masalan, ikkilik daraxt bilan tartiblash har bir elementni n o‘lchamli massivga birma-bir kiritish orqali ikkilik daraxt hosil qiladi. Insert operatsiyasidan beri muvozanatli ikkilik qidiruv daraxti O ni oladi (log n), algoritmning umumiy bajarilish vaqti chiziqli-logarifmik bo'ladi.
Taqqoslash bo'yicha saralash hech bo'lmaganda logdan beri eng yomon holatlardagi taqqoslashlarning chiziqli jurnalini talab qiladi ( n!) = Θ( n jurnal n) Stirling formulasi bo'yicha. Xuddi shu bajarilish vaqti ko'pincha takrorlanish tenglamasidan kelib chiqadi T(n) = 2 T(n/ 2) + O ( n).
Kvadrat vaqt
Polinomli vaqt algoritmlariga ba'zi misollar:
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.