Algoritmlarning vaqt va hajmi boyincha qiyinchiliklar reja

Algoritmlarning vaqt va hajmi boyincha qiyinchiliklar
REJA:
1) Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar.
2) Algoritmlarni eng yomon va o‘rtacha xolatlarda baholash
3) Algoritmlarni vaqt va hajmiy marakkabligini baholashda tekis va logorifmik solishtirma mezonlari.

Algoritmning vaqt murakkabligini baholash. Algoritmlar murakkabligi funksiyalarining turlari

Doimiy vaqt
Algoritmga algoritm deyiladi doimiy vaqt(vaqt sifatida qayd etilgan O (1)) qiymat bo'lsa T(n) kirish hajmiga bog'liq bo'lmagan qiymat bilan cheklangan. Masalan, massivda bitta elementni olish doimiy vaqtni oladi, chunki uni topish uchun bitta buyruq bajariladi. Biroq, tartiblanmagan massivda minimal qiymatni topish doimiy vaqtdagi operatsiya emas, chunki biz massivning har bir elementini skanerlashimiz kerak. Shunday qilib, bu operatsiya chiziqli vaqtni oladi, O (n). Agar elementlarning soni oldindan ma'lum bo'lsa va o'zgarmasa, bunday algoritmni doimiy vaqt algoritmi deb atash mumkin.
"Doimiy vaqt" nomiga qaramay, ish vaqti vazifa hajmidan mustaqil bo'lishi shart emas, lekin ish vaqtining yuqori chegarasi bo'lmasligi kerak. Masalan, "qiymatlarni almashish" vazifasi a va b, zarur bo'lsa, natijada biz olamiz a≤b", doimiy vaqt muammosi hisoblanadi, garchi algoritmning ishlash vaqti tengsizlikning mavjudligiga bog'liq bo'lishi mumkin. a ≤ b yoki yo'q. Biroq, ma'lum bir doimiylik mavjud t, ular uchun vazifani bajarish vaqti har doim oshmaydi t.
Quyida doimiy vaqtda ishlaydigan ba'zi kod misollari keltirilgan:
Int indeksi = 5; int element = ro'yxat; agar(shart to'g'ri) keyinboshqa doimiy ish vaqti bilan ba'zi operatsiyalarni bajarish uchun i = 1 uchun 100 uchun j = 1 uchun 200 doimiy ish vaqti bilan ba'zi operatsiyalarni bajaradi
Agar T(n) bu O ( ba'zi doimiy qiymat), bu ga teng T(n) O (1) dir.
Logarifmik vaqt
logarifmik vaqt, agar T(n) = O (log n) ... Kompyuterlar ikkilik tizimdan foydalanganligi sababli, logarifmning asosi sifatida 2 ishlatiladi (ya'ni log 2). n). Biroq, bilan bazani almashtirish logaritmalar log a n va jurnal b n faqat doimiy koeffitsient bilan farqlanadi, bu esa O-katta belgisida bekor qilinadi. Shunday qilib, O (log n) - logarifm asosidan qat'iy nazar, logarifmik vaqt algoritmlari uchun standart belgi.
Logarifmik vaqt algoritmlari odatda binar daraxt operatsiyalarida yoki ikkilik qidiruvdan foydalanganda topiladi.
O (log n) algoritmlari yuqori samarali hisoblanadi, chunki har bir elementning bajarilish vaqti elementlar sonining ko'payishi bilan kamayadi.
Bunday algoritmning juda oddiy misoli qatorni ikkiga bo'lish, ikkinchi yarmini yana yarmiga bo'lish va hokazo. Bu O (log n) vaqtni oladi (bu erda n - satr uzunligi, biz bu erda taxmin qilamiz console.log va str.substring doimiy vaqt talab qiladi). Bu shuni anglatadiki, nashrlar sonini ko'paytirish uchun chiziq uzunligi ikki barobarga oshirilishi kerak.
// Chiziqning o'ng yarmini rekursiv chop etish funksiyasi var o'ng = funktsiya (str) (var uzunligi = ko'cha uzunligi; // yordamchi funksiya var help = funktsiya (indeks) ( // Rekursiya: o'ng yarmini chop eting agar (indeks< length ) { // Belgilarni indeksdan satr oxirigacha chop etish konsol. log (str. substring (indeks, uzunlik)); // rekursiv chaqiruv: o'ng tomoni bilan yordamchi funksiyani chaqiring yordam (Math.ceil ((uzunlik + indeks) / 2)); )) yordam (0); )
Polilogarifmik vaqt
Algoritm ishga kirishishi aytiladi polilogarifmik vaqt, agar T(n) = O ((log n) k), ba'zilar uchun k... Masalan, matritsalarni ko‘paytirish tartibi masalasini polilogarifmik vaqtda yechish mumkin. parallel PAM mashinasi .
Sublinear vaqt
Algoritm ishga kirishishi aytiladi sublinear vaqt, agar T(n) = o ( n). Xususan, bu yuqorida sanab o'tilgan vaqt murakkabligi algoritmlarini, shuningdek boshqalarni o'z ichiga oladi, masalan, Grover qidiruvi murakkabligi O ( n ½).
To'g'ri bo'lsa-da, hali ham subchiziqli vaqtda ishlaydigan odatiy algoritmlar jarayonlarni parallellashtirishdan (masalan, matritsa determinantini hisoblash uchun NC 1 algoritmida), klassik bo'lmagan hisoblashlardan (Grover qidiruvida bo'lgani kabi) yoki kafolatlangan taxminga ega bo'lgan algoritmlardan foydalanadi. kirishning tuzilishi (logarifmik vaqtda ishlaydigan, ikkilik qidiruv algoritmlari va ko'plab daraxtlarni qayta ishlash algoritmlari). Biroq, satrning birinchi log (n) bitlari tomonidan aniqlangan holatda 1 bitga ega bo'lgan barcha satrlar to'plami kabi rasmiy konstruktsiyalar kirishning har bir bitiga bog'liq bo'lishi mumkin, ammo vaqt o'tishi bilan hali ham pastki chiziqli bo'lib qoladi.
Muddati sublinear ish vaqti algoritmi odatda, yuqoridagi misollardan farqli o'laroq, an'anaviy ketma-ket mashina modellarida ishlaydigan va kirish strukturasi haqida aprior bilimni talab qilmaydigan algoritmlar uchun ishlatiladi. Biroq, ular uchun ehtimollik usullaridan foydalanishga ruxsat beriladi va undan ham ko'proq, algoritmlar eng ahamiyatsiz muammolar uchun ehtimollik bo'lishi kerak.
Bunday algoritm kirish ma'lumotlarini to'liq o'qimasdan javob berishi kerakligi sababli, bu kirish oqimida ruxsat etilgan kirish usullariga juda bog'liq. Odatda bit string oqimi uchun b 1 ,...,b k, algoritm qiymatni so'rashi mumkin deb taxmin qilinadi b i har kim uchun i.
Sublinear vaqt algoritmlari, qoida tariqasida, ehtimollikdir va faqat taxminiy echimni beradi. Sublinear ish vaqti algoritmlari tadqiqot paytida tabiiy ravishda paydo bo'ladi mulkni tekshirish.
Lineer vaqt
chiziqli vaqt, yoki O ( n) agar uning murakkabligi O bo'lsa ( n). Norasmiy ravishda, bu etarli darajada katta kirish hajmi uchun ish vaqti kirish hajmi bilan chiziqli ravishda oshib borishini anglatadi. Masalan, ro'yxatning barcha elementlarini jamlaydigan protsedura ro'yxat uzunligiga proportsional vaqtni oladi. Ushbu tavsif to'liq aniq emas, chunki ish vaqti aniq proportsionallikdan sezilarli darajada farq qilishi mumkin, ayniqsa kichik qiymatlar uchun. n.
Chiziqli vaqt ko'pincha algoritmning kerakli atributi sifatida qaraladi. (deyarli) chiziqli ish vaqti yoki undan yuqori bo'lgan algoritmlarni yaratish uchun ko'plab tadqiqotlar o'tkazildi. Ushbu tadqiqotlar dasturiy ta'minot va apparat yondashuvlarini o'z ichiga oladi. Uskunani bajarish holatida, standart hisoblash modellarida matematik jihatdan hech qachon chiziqli bajarish vaqtiga erisha olmaydigan ba'zi algoritmlar chiziqli vaqtda ishlashi mumkin. Ushbu maqsadga erishish uchun parallellikdan foydalanadigan ba'zi apparat texnologiyalari mavjud. Masalan, assotsiativ xotira. Ushbu chiziqli vaqt tushunchasi Boyer-Mur algoritmi va Ukkonen algoritmi kabi qatorlarni taqqoslash algoritmlarida qo'llaniladi.
Kvazilinear vaqt
Algoritm kvazizikli vaqtda ishlaydi, deyiladi, agar T(n) = O ( n jurnal k n) ba'zi doimiy uchun k... Chiziqli-logarifmik vaqt bilan alohida holat k= 1. Zaif-O belgilaridan foydalanilganda, bu algoritmlar Õ ( n). Kvazilinear vaqt algoritmlari ham o ( n 1 + e) har qanday e> 0 uchun va har qanday polinomdan tezroq ishlaydi n
Yuqorida aytib o'tilgan chiziqli-logarifmik algoritmlarga qo'shimcha ravishda, kvaziziiqli vaqtda ishlaydigan algoritmlarga quyidagilar kiradi:
• O'z joyida birlashtirish tartibi, O ( n jurnal 2 n)
• Tez tartiblash, O ( n jurnal n), ehtimolli versiyada eng yomon holatda chiziqli-logarifmik bajarilish vaqti mavjud. Mumkin bo'lmagan versiyada o'rtacha qiyinchilikni o'lchash uchun chiziqli jurnalning ishlash vaqti mavjud.
• Uyumni tanlash, O ( n jurnal n), birlashma tartiblash, introsort, ikkilik daraxt tartibi, silliq tartiblash, solitaire turi, va hokazo. eng yomoni
• Tez Furye o'zgarishi, O ( n jurnal n)
• Monge matritsalarini hisoblash, O ( n jurnal n)
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.
Qiyinchilik sinflari
Polinom vaqt tushunchasi hisoblash murakkabligi nazariyasida bir necha murakkablik sinflariga olib keladi. Polinom vaqti yordamida aniqlangan ba'zi muhim sinflar quyida ko'rsatilgan.
• : Polinom vaqtida deterministik Tyuring mashinasida echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi.
• : Polinom vaqtida deterministik bo'lmagan Tyuring mashinasida echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi.
• ZPP: Polinom vaqtida ehtimolli Tyuring mashinasida nol xato bilan echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi.
• : Polinom vaqtida ehtimolli Tyuring mashinasida bir tomonlama xatolar bilan echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik klassi.
• BPP polinom vaqtidagi ehtimollik Tyuring mashinasi.
• BQP: Polinom vaqtida kvant Tyuring mashinasida ikki tomonlama xatolar bilan echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik klassi.
P - deterministik mashinadagi eng kichik vaqt murakkabligi sinfi, ya'ni barqaror mashina modelini o'zgartirish nuqtai nazaridan. (Masalan, bitta lentali Tyuring mashinasidan ko'p tarmoqli Tyuring mashinasiga o'tish kvadratik tezlikka olib kelishi mumkin, lekin bir modelda polinom vaqtida ishlaydigan har qanday algoritm boshqasida polinom vaqtida ishlaydi.)
Super polinom vaqti
Algoritm ishlashi aytiladi superpolinom vaqti, agar T(n) yuqorida ko‘phad bilan chegaralanmagan. Bu vaqt ō ga teng ( n c) barcha konstantalar uchun c, qayerda n kirish parametri, odatda kirish bitlari soni.
Masalan, 2 ni amalga oshiradigan algoritm n hajmini kiritish uchun qadamlar n superpolinom vaqtni talab qiladi (aniqrog'i, eksponensial vaqt).
Ko'rsatkichli resurslardan foydalanadigan algoritm superpolinom ekanligi aniq, lekin ba'zi algoritmlar juda zaif superpolinomdir. Masalan, Adleman-Pomeranza-Roumeli soddaligi testi * vaqt uchun ishlaydi n O (jurnal jurnali n) ustida n-bit kiritish. U etarlicha katta bo'lgan har qanday polinomdan tezroq o'sadi n, lekin kirishning o'lchami juda katta bo'lishi kerak, shuning uchun u kichik darajadagi polinom tomonidan hukmronlik qilmasligi kerak.
Superpolinom vaqt talab qiladigan algoritm murakkablik sinfidan tashqarida. Kobhamning tezislari bu algoritmlar amaliy emas, deb da'vo qiladi va ko'p hollarda ular. P va NP sinflarining tengligi masalasi hal etilmaganligi sababli, hozirgi vaqtda NP-to'liq masalalarni polinom vaqtida yechish algoritmlari ma'lum emas.
Kvazi-polinomli vaqt
Algoritmlar kvazi-polinomli vaqt Bu algoritmlar polinom vaqtidan sekinroq ishlaydi, lekin eksponensial vaqt algoritmlari kabi sekin emas. Kvazi-polinomli algoritm uchun eng yomon ish vaqti c... Butun sonni omillarga ajratish uchun taniqli klassik algoritm, emas kvazi-polinom hisoblanadi, chunki ish vaqtini quyidagicha ifodalab bo'lmaydi 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c)))) ba'zilari uchun sobit c... Kvazipolinomli vaqt algoritmi ta'rifidagi doimiy "c" 1 ga teng bo'lsa, ko'p nomli vaqt algoritmini, 1 dan kichik bo'lsa, pastki chiziqli vaqt algoritmini olamiz.
Kvazi-polinomli vaqt algoritmlari odatda NP-qiyin muammoni boshqa masalaga qisqartirganda paydo bo'ladi. Masalan, siz NP uchun qiyin masalani qabul qilishingiz mumkin, masalan, 3SAT va uni boshqa B muammosiga qisqartirishingiz mumkin, ammo muammoning hajmi kattalashadi. 2 O ((log ⁡ n) c) (\ displaystyle 2 ^ (O ((\ log n) ^ (c))))... Bunday holda, qisqartirish B muammosi NP-qiyin ekanligini isbotlamaydi; bunday qisqartirish faqat B uchun polinom algoritmi yo'qligini ko'rsatadi, agar 3SAT uchun kvazipolinomli algoritm mavjud bo'lmasa (va keyin barcha muammolar uchun). Xuddi shunday, ba'zi muammolar mavjud bo'lib, ular uchun biz kvazi-polinomli vaqtli algoritmlarni bilamiz, lekin ular uchun ko'p nomli vaqtli algoritmlar noma'lum. Bunday muammolar taxminiy algoritmlarda paydo bo'ladi. Mashhur misol - Shtaynerning yo'naltirilgan muammosi bo'lib, u uchun yaqinlashish koeffitsientiga ega bo'lgan taxminiy kvazi-polinom algoritmi mavjud. O (log 3 ⁡ n) (\ displaystyle O (\ log ^ (3) n))(bu erda n - cho'qqilar soni), lekin ko'p nomli vaqt algoritmining mavjudligi ochiq muammodir.
Qiyinchilik klassi QP kvazi-polinomli vaqt algoritmlari bilan bog'liq barcha masalalardan iborat. Uni DTIME nuqtai nazaridan quyidagicha aniqlash mumkin
QP = ⋃ c ∈ N DTIME (2 (log ⁡ n) c) (\ displaystyle (\ mbox (QP)) = \ bigcup _ (c \ in \ mathbb (N)) (\ mbox (DTIME)) (2 ^ ((\ log n) ^ (c))))
NP-to'liq muammolar bilan munosabatlar
Murakkablik nazariyasida P va NP sinflari orasidagi tenglikning yechilmagan muammosi NP sinfidagi barcha masalalarni polinom vaqtida yechish algoritmlari borligini so'raydi. 3SAT kabi NP-to'liq muammolar uchun barcha taniqli algoritmlar eksponensial vaqtga ega. Bundan tashqari, ko'pgina tabiiy NP-to'liq muammolar uchun subeksponensial bajarish vaqti bilan algoritmlar mavjud emas degan gipoteza mavjud. Bu yerda “subeksponensial vaqt” quyidagi ikkinchi taʼrif maʼnosida olingan. (Boshqa tomondan, tabiiy ravishda qo'shni matritsalar bilan ifodalangan ko'plab grafik nazariyasi muammolari subeksponensial vaqtda echilishi mumkin, chunki kirishning o'lchami cho'qqilar sonining kvadratiga tengdir.) Bu gipoteza (k-SAT muammosi uchun) sifatida tanilgan eksponensial vaqt gipotezasi... NP-to'liq masalalarda kvazi-polinomli vaqt algoritmlari mavjud emas deb taxmin qilinganligi sababli, ba'zi bir yaqinlashmaslik natijalari yaqinlashish algoritmlari sohasiga olib keladi, NP-to'liq masalalarda kvazi-polinomli vaqt algoritmlari mavjud emas deb taxmin qilinadi. Misol uchun, to'plamni qoplash muammosining yaqinlashmasligi haqidagi taniqli natijalarga qarang.
Subeksponensial vaqt
Muddati subeksponensial vaqt ba'zi algoritmlarning bajarilish vaqti har qanday ko'phadga qaraganda tezroq o'sishi mumkinligini ifodalash uchun ishlatiladi, lekin u eksponensialdan sezilarli darajada kamroq bo'lib qoladi. Shu ma'noda, subeksponensial vaqt algoritmlari bilan bog'liq muammolar faqat eksponensial vaqtli algoritmlarga qaraganda ancha moslashuvchan. "Sub-eksponensial" ning aniq ta'rifi hali umumiy qabul qilinmagan va biz quyida eng keng tarqalgan ikkita ta'rifni keltiramiz.
Birinchi ta'rif
Agar muammo ish vaqtining logarifmi har qanday berilgan ko‘phaddan kamroq o‘sadigan algoritm bilan yechilsa, muammo subeksponensial vaqtda yechilgan deyiladi. Aniqroq qilib aytadigan bo'lsak, har qanday e> 0 uchun muammoni O (2 n e) vaqtida hal qiluvchi algoritm mavjud bo'lsa, masala subeksponensial vaqtga ega bo'ladi. Bunday masalalarning barchasi murakkablik sinfini tashkil qiladi SUBEXP, bu DTIME jihatidan ifodalanishi mumkin.
SUBEXP = ⋂ e> 0 DTIME (2 n e) (\ displaystyle (\ text (SUBEXP)) = \ bigcap _ (\ varepsilon> 0) (\ text (DTIME)) \ chap (2 ^ (n ^ (\ varepsilon) ))) \ to'g'ri))
E'tibor bering, bu erda e kiritilgan ma'lumotlarning bir qismi emas va har bir e uchun muammoni hal qilishning o'ziga xos algoritmi bo'lishi mumkin.
Ikkinchi ta'rif
Ba'zi mualliflar subeksponensial vaqtni ish vaqti sifatida belgilaydilar 2 o ( n). Ushbu ta'rif birinchi ta'rifdan ko'ra uzoqroq ishlashga imkon beradi. Bunday subeksponensial vaqt algoritmiga misol sifatida butun sonlarni omillarga ajratishning mashhur klassik algoritmi, taxminan 100 ga yaqin vaqtni tashkil etadigan umumiy sonli maydon elak usulini keltirish mumkin. 2 O ~ (n 1/3) (\ displaystyle 2 ^ ((\ tilde (O)) (n ^ (1/3))), kirishning uzunligi qaerda n... Yana bir misol uchun mashhur algoritm Grafik izomorfizm masalalari kimning ish vaqti 2 O ((n log ⁡ n)) (\ displaystyle 2 ^ (O ((\ sqrt (()) n \ log n)))).
E'tibor bering, bu algoritm cho'qqilar sonida yoki qirralarning sonida sub-eksponensial bo'ladimi, farq qiladi. V parametrlangan murakkablik bu farq juftlik, echilish muammosi va parametrni ko'rsatish orqali aniq namoyon bo'ladi k. SUBEPT yilda subeksponensial vaqtda bajariladigan barcha parametrlangan masalalar sinfidir k va polinom uchun n :
SUBEPT = DTIME (2 o (k) ⋅ poli (n)). (\ displaystyle (\ text (SUBEPT)) = (\ text (DTIME)) \ chap (2 ^ (o (k)) \ cdot (\ matn (poli)) (n) \ o'ng).)
Aniqroq aytganda, SUBEPT barcha parametrlangan vazifalar sinfidir (L, k) (\ displaystyle (L, k)) buning uchun hisoblash funktsiyasi mavjud f: N → N (\ displaystyle f: \ mathbb (N) \ to \ mathbb (N)) Bilan f ∈ o (k) (\ displaystyle f \ in o (k)) va hal qiluvchi algoritm L davomida 2 f (k) ⋅ poli (n) (\ displaystyle 2 ^ (f (k)) \ cdot (\ matn (poli)) (n)).
2-bob. Algoritmlarning murakkabligi.
2.1 Algoritmlarning vaqt va hisoblash murakkabligi.
Algoritmning vaqt murakkabligi (T(N) , qayerda N- topshiriqning o'lchami) - qadamlar bilan o'lchanadigan algoritmning bajarilish vaqti (natijaga erishish uchun bajarilishi kerak bo'lgan algoritm ko'rsatmalari). Ya'ni, bu muammoni hal qilish algoritmini tashkil etuvchi elementar operatsiyalar soni (: =,<>, =, +, -, *, /; va, yoki, emas, xor; qo'ng'iroq qilish, qaytish).
Muammoni hal qilishda kiritilgan ma'lumotlarning kombinatsiyasiga (ekvivalentligi, siyrakligi, tartibliligi va kiritilgan ma'lumotlarning boshqa xususiyatlari) bog'liq bo'lgan uch xil vaqt murakkabligi mavjud.
https://pandia.ru/text/78/183/images/image002_151.gif "kenglik =" 178 balandlik = 60 "balandlik =" 60 ">
Bo‘lyapti T(N)= C* N2 kvadrat matritsa uchun amal qiladi.
Bu holda elementar operatsiyalar "+" va "*" kombinatsiyasi hisoblanadi.
Agar asl matritsa identifikatsiya bo'lsa, biz eng yaxshi holatni olamiz.
Agar matritsada elementlarning yarmi 0, yarmi 1 bo'lsa, biz O'rtacha holatni olamiz.
Doimiy BILAN, aniq ifodalab bo'lmaydigan, tashqi omillarning algoritmlarni bajarish vaqtiga ta'sirini tavsiflaydi (kompyuter tezligi, kompilyatsiya tezligi). Shuning uchun algoritmlarning vaqt murakkabligini baholash uchun vaqt birliklaridan foydalanish mutlaqo to'g'ri emas. Bu holda matritsa-vektorni ko'paytirish algoritmining vaqt murakkabligi ga proportsional deyiladi. N2 .
2.2 Ova Ō - belgilar.
Vaqt murakkabligining xulq-atvorining tabiati ortib borayotganida N (N® ¥ ) chaqirdi algoritmning asimptotik murakkabligi.
Asimptotik murakkablikning o'sish tezligini tavsiflash uchun biz foydalanamiz O-notatsiyasi. Algoritmning vaqt murakkabligi tartibida deyilganda N2 :
T(N)= O(N2 )= O(f(N)),
Keyin musbat konstantalar borligi taxmin qilinadi C, n0 =const (C>0), hamma uchun shunday N ³ N0 tengsizlik amal qiladi
T(N) £ C* f(N)
Bu murakkablik bahosining yuqori chegarasi.
2-misol:
Mayli T (0) = 1, T (1) = 4, ..., T (N)=(N+1) 2, keyin bu algoritmning vaqt murakkabligi o'sish tartibida bo'ladi T(N)= O(N2 ).
Buni hamma uchun ko'rsatish mumkin N > n0 da n0 = 1, C = 4 tengsizlik (1) bajariladi.
(N+1)2 £ 4* N2
3-misol:
Vaqt murakkabligi polinom sifatida yozilsa
T(N)= C1 N2 + C2 N+ C3 ,
u holda bunday algoritm polinomning maksimal elementi darajasiga karrali murakkablik tartibiga ega, chunki u eng tez o'sadi. N® ¥ :
T(N)= O(N2 ).
Masalan:
3 n2 +5 n+1 £ 5 n2
" n ³ 1
4-misol:
Agar ba'zi bir algoritm bir nechta murakkablikka ega bo'lsa 3 n, u holda tezlikning o'sish tartibi ko'paytmali bo'lishi mumkin emasligini ko'rsatish mumkin O(2 n):
T(N)=3 n¹ O(2 n).
Doimiylar bo'lsin C, n0 , shunday qilib, quyidagi tengsizlik amal qiladi:
3n £ C*2 n, n > n0 .
Bu erdan biz olamiz:
BILAN³ (3/2)2, n > n0 .
Lekin bilan n® ¥ bunday doimiy mavjud emas BILAN bu tengsizlikni qondiradi.
Murakkablikning yuqori chegarasidan tashqari, vaqtinchalik murakkablikning o'sish tezligining pastki chegarasi ham mavjud:
T(N) ³ V(f(N))
Tengsizlik (2) qandaydir doimiy borligini bildiradi BILAN buning uchun N® ¥ vaqt murakkabligi
T(N) ³ C* f(N).
T (N) (asimptotik vaqt murakkabligi) ni aniq aniqlashning murakkabligini hisobga olgan holda, dastlabki ma'lumotlarning hajmiga qarab, amalda algoritmning vaqt murakkabligining pastki va yuqori chegaralari qo'llaniladi:

T(N) = q (f(N))

Konstantaning qiymatiga qarab BILAN algoritm murakkabligining o'sish tezligi sezilarli darajada farq qilishi mumkin.
5-misol:
Vaqt murakkabligi formula bilan yozilsin
T (N) = 3n2 –100n + 6 = O (n2)
3n2> 3n2 –100n + 6, n³ 1, C = 3.
Agar C1» 0 (C1 = 0,00001), keyin tengsizlik
10-5 n2 > 3 n2 –100 n+6, n³ 1
bajarilmagan.
Ammo murakkablikning o'sish tartibini ko'rsatish mumkin
3n2 –100n + 6¹ O (N).
C * N< 3N2, N>C.
3n2 –100n + 6 = (n2)
C=2.29, n ³ n0.
2.99* n2 < 3 n2 –100 n+6
Pastki chegara ekanligini ko'rsatish mumkin
3 n2 –100 n+6 ¹ V(n3 ) da C = 1.
Tengsizlik 3 n2 –100 n+6 ³ n3 bajarilmagan.
3 n2 –100 n+6= V(n)
C1 = , n> n0 .
https://pandia.ru/text/78/183/images/image007_89.gif "kenglik =" 305 "balandlik =" 247 src = ">
f1 (N)=100 n2
f2 (N)=5 n3
n0 =20 – tanqidiy nuqta.
Murakkablik darajasi pastroq bo'lgan algoritmlarga ustunlik berishning yana bir sababi shundaki, murakkablik tartibi qanchalik past bo'lsa, masalaning hajmi shunchalik katta bo'ladi. N amaliy jihatdan hal qilish mumkin.
0 "style =" margin-left: 5,4pt; chegarani yig'ish: yig'ish; chegara: yo'q ">
n!
6-misol:
Shuni yodda tutish kerakki, algoritmlarning murakkabligi o'sishining katta tartibi, qoida tariqasida, kichikroq konstantaga ega. C1 doimiy bilan xarakterlanadi murakkabligi o'sish kichik tartibi bilan solishtirganda C2.
Bunday holda, kichik hajmdagi muammolarni hal qilish uchun tez o'sib borayotgan murakkablikdagi algoritm afzalroq bo'lishi mumkin ( n® 0 ).
Xuddi shu muammoni hal qilishda qiyinchiliklarga duch keladigan beshta algoritm berilsin:
A1: 100 N
A2: 100 N* logN
A3: 10 N2
A4: N3
A5: 2 N
Keyin, bilan bog'liq muammolar uchun N=2 ¸ 9 tezroq A5 bo'ladi ( f(N) ~ 4 ¸ 512 ). Boshqa algoritmlar, almashtirilganda, sezilarli darajada pastroq stavkalarni beradi.
Da N=10 ¸ 58 A3 ga afzallik beriladi.
Da N=59 ¸ 1024 eng samarali A2 bo'ladi.
Da N>1024 A1 ga afzallik beriladi.
Bir nechta ketma-ket yoki bir vaqtda bajariladigan algoritmlardan tashkil topgan dasturlar uchun murakkablik quyidagicha baholanadi: summa qoidasi va ishlar qoidasi.