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.

Jamlama qoidasi : Dastur ikkita ketma-ket bajariladigan R1 va R2 algoritmlaridan iborat bo'lsin, ular uchun qiyinchiliklar aniqlanadi. O(f(n)) va O(g(n)) mos ravishda. Keyin butun dasturning vaqt murakkabligi algoritmlarning har birining vaqt murakkabligi yig'indisi sifatida aniqlanadi:

T(n) = T1 (n)+ T2 (n)

Umuman olganda, biz quyidagilarni olamiz:

T (n)Þ O (maksimal f (n), g (n))

Ishlar qoidasi: Murakkablik tartibi bilan ikkita parallel bajaruvchi algoritmdan tashkil topgan dasturning vaqt murakkabligi bo'lsin. O(f(n)) va O(g(n)) Shunga ko'ra, u algoritmlarning har birining vaqt murakkabligi mahsuloti sifatida aniqlanadi:

T(n) = T1 (n)* T2 (n)

Umuman:

T(n) Þ O(f(n)* g(n))

Logarifmlar.

2.3. Rekursiya.

Algoritmik tuzilmalarni joylashtirish tufayli rekursiv algoritmlarning murakkabligini baholash oson emas.

f(n) Þ f(n* f(n-1))

Masalan, n algoritmini rekursiv baholash uchun! Murakkablik rekursiyaga kiritilgan har bir algoritmning murakkabligiga bog'liq bo'ladi.

Umuman T(n) ~ O(N).

Boshqa rekursiv algoritmlar odatda vaqt murakkabligiga ega T(n) ~ O(a) , qayerda a= const, bu bir xil masalani yechish uchun rekursiv bo'lmagan algoritmning murakkabligidan kattaroq umumiy murakkablikka olib keladi.

2.4 Algoritm va dasturlarning murakkabligini baholash.

2.4.2 Bog'liqlikni tiklash algoritmlari.

Ba'zi hollarda dasturning tuzilishi noma'lum va siz faqat turli o'lchamdagi kirish ma'lumotlari uchun uning ishlash vaqtini aniqlashingiz mumkin. T(N) (sek.)

Dasturning, funksiyaning murakkabligining analitik bog'liqligini qurish T(N) ba'zi bir intervalda [ Nmin, Nmax] ... Keyinchalik, ba'zi bir analitik funktsiyaning topilgan egri chizig'i funksiya parametrlarining o'zgarishi va yaqinlashish xatosining taxmini bilan yaqinlashtiriladi.

Qoida tariqasida, vaqt murakkabligining taniqli funktsiyalari bunday funktsiya sifatida ishlatiladi: O(n!), O(XN), O(NX), O(logN), O(https://pandia.ru/text/78/183/images/image010_72.gif "width =" 307 "height =" 225 src = "> Dasturda o'tkazilgan tajriba natijasida vaqt qiyinchiliklari jadvali tuzildi. olingan:

Funktsiyaning yaqinlashishini izlash natijasida quyidagi analitik bog'liqlik olindi:

https://pandia.ru/text/78/183/images/image012_68.gif "kenglik =" 321 "balandlik =" 143 src = ">

2-misol:

Ko'pincha shunday bo'ladiki, bir xil algoritmning ishlash vaqti, muammoning o'lchamidan tashqari, foydalanuvchi kiritgan boshqa parametrlarga ta'sir qiladi.

Bunda yaqinlashuv funksiyalari oilasi tuziladi va algoritmning murakkabligi analitik yo‘l bilan topiladi.

Mehnat intensivligi "href =" / matn / kategoriya / trudoemkostmz / "rel =" xatcho'p "> mehnat zichligi (ish vaqti).

Algoritmning polinom yoki eksponensial tabiati kiritilgan ma'lumotlarning shakliga (ikkilik, o'nlik yoki boshqa sanoq sistemasi) nisbatan o'zgarmasdir.

Algoritmning ishlash vaqti, ya'ni vaqt murakkabligi yuqoridan ma'lum darajada ko'phad bilan chegaralangan bo'lsa, u ko'pnomli deyiladi. T(N)= O(Nm) ... Keyin bunday algoritm bilan yechilgan barcha masalalar P-sinf masalalarni tashkil qiladi. Bu vazifalar R.ga kiritilganligi aytiladi.

Eksponensial vaqt murakkabligi bilan bog'liq muammolar ( T(N)= O(KN) ) R ga kiritilmagan.

Izoh : Chiziqli murakkablikdagi masalalar P ga kiritilganligini ko'rsatish mumkin

T(N)= O(N1 )

Keling, deterministik bo'lmagan algoritm yordamida polinom vaqtida yechish mumkin bo'lgan NP-muammolar sinfini kiritamiz.

Algoritm holatini hozirda bajarilayotgan buyruq manzili va jarayon holati vektoriga ekvivalent bo'lgan barcha o'zgaruvchilar qiymatlari to'plami sifatida belgilaymiz. Shuning uchun ko'pchilik algoritmlar deterministikdir, ya'ni ularda har qanday holat uchun faqat bitta ruxsat etilgan keyingi holat (shart va tanlash operatsiyalari) mavjud. Bu shuni anglatadiki, bunday algoritm bir vaqtning o'zida bitta ishni bajarishi mumkin.

V deterministik bo'lmagan algoritm (NDA) har qanday holat uchun bir nechta ruxsat etilgan keyingi holat bo'lishi mumkin, ya'ni bunday algoritm bir vaqtning o'zida bir nechta operatorni bajarishi mumkin.

NDA tasodifiy yoki ehtimolli algoritm emas. Bu ko'plab shtatlarda bo'lishi mumkin bo'lgan algoritmdir (bu ko'plab variantlar bilan parallel ravishda muammoni hal qilishga teng).

Misol:

Deterministik algoritm (DA) bu muammoni ketma-ket hal qiladi (barcha variantlarni sanab o'tish, A0 muqobilini tanlamaguncha optimallik mezoni K0 bilan taqqoslash).

NDA bir vaqtning o'zida (parallel ravishda) barcha muqobillarni olishi va K0 bilan solishtirishi mumkin, mustaqil ravishda amalga oshiriladigan har bir muqobil uchun alohida jarayon sifatida o'zini nusxalash.

Bunday holda, agar biron bir nusxa noto'g'ri natija olinganligini yoki natija olinmaganligini aniqlasa, u bajarilishini to'xtatadi. Agar nusxa K0 ni qanoatlantiradigan yechim topsa, u muvaffaqiyatni e'lon qiladi va boshqa barcha nusxalar ishlashni to'xtatadi.

Bu. NDA uchta parametr bilan tavsiflanadi:

1. tanlash- qiymatlari S to'plamining elementlari bo'lgan ko'p qiymatli funktsiya;

2. muvaffaqiyatsizlik algoritm nusxasini tugatishga olib keladi;

3. muvaffaqiyat algoritmning barcha nusxalarini tugatishga va natijaga olib keladi.

Shubhasiz, hech qanday jismoniy qurilma cheksiz deterministik bo'lmagan xatti-harakatlarga qodir emas, bu NDA nazariy usul ekanligini anglatadi.

NDA polinom yordamida echilishi mumkin bo'lgan masalalar NP-muammolar sinfini tashkil qiladi.

2.5.2 NP- qiyin vaNP- Vazifalarni bajaring.

P dagi muammo NP- qiyin agar uning yechimining DA (PDA) polinomi mavjud bo'lsa, undan NPga kiritilgan barcha masalalarning yechimini olish uchun foydalanish mumkin. Ya'ni, bunday muammo NP-qiyin, agar u hech bo'lmaganda NPdagi har qanday muammo kabi qiyin bo'lsa.

NP ga tegishli NP-qiyin masala deyiladi NP-to'la vazifa. Bunday muammolar har qanday NP muammosidan kam emas. Bundan tashqari, NP-qattiq yoki NP-to'liq masala uchun PDA mavjudligi P va NP sinflarining mos kelishini anglatadi, ya'ni 3-sinfning barcha masalalarini tezkor algoritm bilan hal qilish mumkin.

Muammoning NP-qiyinligini isbotlash uchun, agar muammo uchun PDA mavjud bo'lsa, u holda NPga kiritilgan muammolarning boshqa PDA yechimini olish uchun ishlatilishi mumkinligini ko'rsatish kerak.

Muammoning NP-to'liq ekanligini aniqlash uchun uning NPga tegishli ekanligini isbotlash kerak.

Bir masalani yechish algoritmidan boshqasini yechish algoritmini olish uchun foydalanish g‘oyasi algoritmlar nazariyasidagi eng muhim algoritmlardan biridir.

Ta'rif 1: R1 masala R2 muammosiga aylantiriladi, agar R1 muammoning har qanday maxsus holatini ko'pnomli vaqtda R2 muammosining qandaydir maxsus holatiga aylantirish mumkin bo'lsa. U holda R1 yechimini R2 muammoning xususiy holining yechimidan ko‘pnomli vaqtda olish mumkin.

https://pandia.ru/text/78/183/images/image024_39.gif "kenglik =" 158 balandlik = 56 "balandlik =" 56 ">

Masalan:

f2 (xi)=(x1 Ú x2 ) Ù ( ) Ù ()

mumkin emas, chunki hech kim uchun xi f2 (xi)= yolg'on.

Teorema :

Qoniqish muammosi NP-to'liq.

xi tanlash (to'g'ri, noto'g'ri)

agar E (x1, x2,…, xN) bo'lsa, muvaffaqiyat

boshqa muvaffaqiyatsizlik

P1 muammosini P2 ga aylantirishdan foydalanib, qoniqish muammosining cheklangan holati ham NP-to'liq ekanligini ko'rsatish mumkin.

K - amalga oshirish imkoniyati .

K-qoniqarliligi CNFga kiritilgan har qanday bandda ko'pi bilan K mantiqiy o'zgaruvchilar mavjudligini anglatadi.

Minimal holat K = 3. CNFda ifodalangan mantiqiy funktsiya uchun polinom vaqtida funktsiyani topish mumkin E * (x2) har bir bandda ko'pi bilan uchta o'zgaruvchini o'z ichiga oladi. Keyin E amalga oshirish mumkin bo'lsa E *.

E* (x1 , x2 ,…, xn) ® E* (xi)

Buning uchun band tartibini kamaytirish usuli qo'llaniladi

(a1 Ú a2 Ú … Ú ak)=(a1 Ú a2 Ú z) Ù (a3 Ú a4 Ú … Ú ak Ú )

Iterativ parchalanish jarayonini qo'llash orqali olish mumkin E *.

Yechim algoritmini toping E * funksiyalarga qaraganda oddiyroq E... Ammo shu bilan birga, maqsadga muvofiqligini isbotladi E *, biz asl funktsiyaning qoniqarliligini isbotlaymiz E.

Maxsus holat: K = 2 uchun funktsiya E R ga kiritilgan.

NP-sinf muammolariga misollar ham grafik muammolar :

1) Yo'naltirilmagan grafikning kliklarining maksimalini aniqlash (NP-qiyin masala).

2) To'liq subgrafani aniqlash masalasi (NP-to'liq muammo).

3) Yo'naltirilmagan grafik uchun L kardinallikning cho'qqi qoplamasini aniqlash (NP-to'liq muammo).

4) Yo'naltirilmagan grafikning maksimal cho'qqi qoplamalarini aniqlash (NP-qiyin masala).

5) Grafik uchun Gamilton siklining mavjudligini aniqlash masalasi (NP-to'liq masala).

6) Sayohatchi sotuvchi muammosi: Har bir cho'qqida bitta hodisa bilan grafik bo'ylab optimal harakatni aniqlash (NP-qiyin muammo).

7) Rejalashtirish muammosi (NP-to'liq muammo).

2.6 Algoritmik yechilmaydigan masalalar

Muammolarni baham ko'ring yolg'iz va katta.

Masalan:

5 + 7 =? Yagona muammo.

x + y =? Katta muammo.

Paradoksal bo'lgan ob'ektlarni olish yoki paradoksal ob'ektlar mavjud bo'lgan muammolarni hal qilish algoritmlari tubdan hal qilib bo'lmaydigan bo'lishi kerak.

Masalan, paradokslar:

1-misol:

Hilbertning 10-muammosi.

D. Gilbert 1901 yilda diofant tenglamalarini yechishda quyidagi masalani ilgari suradi:

Ixtiyoriy Diofant tenglamasi uchun qandaydir butun son yechimini aniqlaydigan algoritmni toping.

F(x, y, …)=0

Bu noma'lumlar uchun butun ko'rsatkichli va butun son koeffitsientli polinom

anxn + an-1xn-1 +… + a2x2 + a1x + a0 = 0

Yuqoridagi tenglama uchun ma'lum bir yechim mavjud bo'lib, u har bir butun son ildizidan iborat xi bo'luvchi hisoblanadi a0 ... Qayerda a0 asosiy omillarga ajrating va har bir omilni ildizga muvofiqligini tekshiring.

1970 yilda leningradlik matematik Yu.Matiyasevich Diofant tenglamasini umumiy shaklda yechishning algoritmik imkonsizligini matematik tarzda isbotladi.

2-misol:

Ferma teoremasi:

Bunday butun sonlar mavjud emas a, b, s, n (n>2) buning uchun tenglik

a + bn = cn

Bu teorema ko'p qiymatlar uchun isbotlangan n va maxsus holatlar uchun tekshiriladi, lekin teoremaning umumiy isboti hali yaratilmagan.

3-misol:

Goldbax muammosi.

X. Xolbax 1742 yilda Eylerga yo‘llagan maktubida muammoni shunday shakllantirgan:

Har bir butun sonni isbotlang N³ 6 uchta tub sonning yig'indisi sifatida ifodalanishi mumkin

N= a+ b+ c

Bu shuni anglatadiki, siz har qanday butun songa ruxsat beradigan algoritmni topishingiz kerak N³ 6 kamida bitta parchalanishni uchta oddiy atamaga toping.

Eyler bu muammoni tez-tez hal qilishni taklif qildi: hatto uchun N bu muammo echilishi mumkin va ikkita oddiy atamaga parchalanishga teng.

I. Vinogradov 1937 yilda buni g'alati ekanligini isbotladi N uchta oddiy atamani topish mumkin, lekin juft sonlar uchun yechim hali topilmagan.

O (1) - Dasturdagi amallarning aksariyati faqat bir marta yoki bir necha marta bajariladi. Doimiy murakkablik algoritmlari. Ma'lumotlar hajmidan qat'i nazar, har doim bir xil vaqtni talab qiladigan har qanday algoritm doimiy murakkablik.

O (N) - Dasturning ishlash vaqti chiziqli odatda kirishning har bir elementi faqat chiziqli marta qayta ishlanishi kerak bo'lganda.

O (N 2), O (N 3), O (N a) - Polinom murakkabligi.

O (N 2) -kvadrat murakkablik, O (N 3) - kubik murakkablik

O (Log (N)) - Dastur qachon ishlaydi logarifmik, dastur N ortishi bilan ancha sekinroq ishlay boshlaydi. Bunday ish vaqtlari odatda katta masalani kichiklarga ajratadigan va ularni alohida yechiydigan dasturlarda uchraydi.

O (N * log (N)) - Bunday ish vaqti o'sha algoritmlarga ega katta muammoni kichikga bo'lish, va keyin ularni hal qilib, ularning echimlarini birlashtiring.

O (2 N) = Eksponensial murakkablik. Bunday algoritmlar ko'pincha qo'pol kuch deb ataladigan yondashuvdan kelib chiqadi.

Dasturchi algoritmlarni tahlil qilish va ularning murakkabligini aniqlay olishi kerak. Algoritmning vaqt murakkabligini uning boshqaruv tuzilmalarini tahlil qilish asosida hisoblash mumkin.

Loopsiz va rekursiv chaqiruvlarsiz algoritmlar doimiy murakkablikka ega. Agar rekursiya va looplar bo'lmasa, barcha boshqaruv tuzilmalari doimiy murakkablikdagi tuzilmalarga qisqartirilishi mumkin. Binobarin, butun algoritm ham doimiy murakkablik bilan tavsiflanadi.

Algoritmning murakkabligini aniqlash, asosan, tsikllar va rekursiv chaqiruvlarni tahlil qilishga qisqartiriladi.

Masalan, massiv elementlarini qayta ishlash algoritmini ko'rib chiqing.
i uchun: = 1 dan N gacha
Boshlash
...
Oxiri;

Ushbu algoritmning murakkabligi O (N), chunki sikl tanasi N marta bajariladi va sikl tanasining murakkabligi O (1) ga teng.

Agar bir sikl boshqasiga o'rnatilgan bo'lsa va ikkala tsikl ham bir xil o'zgaruvchining o'lchamiga bog'liq bo'lsa, unda butun qurilish kvadratik murakkablik bilan tavsiflanadi.
i uchun: = 1 dan N gacha
j uchun: = 1 dan N gacha
Boshlash
...
Oxiri;
Ushbu dasturning murakkabligi O (N 2).

Mavjud Algoritmning murakkabligini tahlil qilishning ikkita usuli: pastdan yuqoriga (ichki boshqaruv tuzilmalaridan tashqi tuzilmalargacha) va tushayotgan (tashqi va ichki tomondan).

O (H) = O (1) + O (1) + O (1) = O (1);
O (I) = O (N) * (O (F) + O (J)) = O (N) * O (shart dominantlari) = O (N);
O (G) = O (N) * (O (C) + O (I) + O (K)) = O (N) * (O (1) + O (N) + O (1)) = O (N 2);
O (E) = O (N) * (O (B) + O (G) + O (L)) = O (N) * O (N 2) = O (N 3);
O (D) = O (A) + O (E) = O (1) + O (N 3) = O (N 3)

Bu algoritmning murakkabligi O (N 3).

Qoida tariqasida, dasturning ishlash vaqtining taxminan 90% takrorlashni talab qiladi va faqat 10% to'g'ridan-to'g'ri hisoblanadi. Dasturlarning murakkabligini tahlil qilish shuni ko'rsatadiki, qaysi qismlar ushbu 90% ga to'g'ri keladi - bular eng katta chuqurlikdagi tsikllardir. Takrorlashlar o'rnatilgan halqalar yoki ichki rekursiya sifatida tashkil etilishi mumkin.

Ushbu ma'lumotlardan dasturchi samaraliroq dastur yaratish uchun quyidagi tarzda foydalanishi mumkin. Avvalo, takrorlashning chuqurligini kamaytirishga harakat qilishingiz mumkin. Keyin eng chuqur halqalardagi bayonotlar sonini kamaytirish haqida o'ylashingiz kerak. Agar bajarilish vaqtining 90% ichki halqalarni bajarishda bo'lsa, u holda bu kichik bo'limlarning 30% ga qisqarishi butun dasturni bajarish vaqtining 90% * 30% = 27% qisqarishiga olib keladi.

Bu eng oddiy misol.

Matematikaning alohida bo'limi algoritmlarning samaradorligini tahlil qilish bilan shug'ullanadi va eng maqbul funktsiyani topish unchalik oson emas.

Keling, baho beramiz massivdagi ikkilik qidiruv algoritmi - dixotomiya.

Algoritmning mohiyati: biz massivning o'rtasiga o'tamiz va kalitning o'rta element qiymatiga mos kelishini qidiramiz. Agar moslikni topa olmasak, biz kalitning nisbiy hajmi va median qiymatini ko'rib chiqamiz va keyin ro'yxatning pastki yoki yuqori yarmiga o'tamiz. Bu yarmida biz yana o'rtani qidiramiz va yana kalit bilan taqqoslaymiz. Agar u ishlamasa, joriy intervalni yana yarmiga bo'ling.

funktsiyani qidirish (past, yuqori, kalit: integer): butun;
var
o'rta, ma'lumotlar: butun son;
boshlash
past bo'lganda<=high do
boshlash
o'rta: = (past + yuqori) div 2;
ma'lumotlar: = a;
agar kalit = ma'lumotlar bo'lsa
qidiruv: = o'rta
boshqa
kalit bo'lsa< data then
yuqori: = o'rta-1
boshqa
past: = o'rta + 1;
oxiri;
qidiruv: = - 1;
oxiri;

Loopning birinchi iteratsiyasi butun ro'yxat bilan bog'liq. Har bir keyingi iteratsiya pastki ro'yxat hajmini yarmiga qisqartiradi. Shunday qilib, algoritm uchun ro'yxatning o'lchamlari

n n / 2 1 n / 2 2 n / 2 3 n / 2 4 ... n / 2 m

Oxirida shunday m butun soni bo'ladi

n / 2 m<2 или n<2 m+1

Chunki m n / 2 m bo'lgan birinchi butun sondir<2, то должно быть верно

n / 2 m-1> = 2 yoki 2 m =

Bundan kelib chiqadi
2 m = Tengsizlikning har bir qismining logarifmini olamiz va olamiz
m = m qiymati = bo'lgan eng katta butun sondir<х.
Shunday qilib, O (log 2 n).

Odatda hal qilinayotgan muammoning tabiiy “o‘lchami” (odatda u ishlov beradigan ma’lumotlar miqdori) bo‘ladi, biz uni N deb ataymiz. Oxir oqibat, biz N o‘lchamdagi ma’lumotlarni qayta ishlash uchun dastur uchun zarur bo‘lgan vaqt uchun ifodani olishni istaymiz. funksiyasi N. Odatda bizni o'rtacha holat qiziqtirmaydi - "odatiy" kirishlar bo'yicha dasturning kutilayotgan ish vaqti, eng yomoni esa eng yomon kiritish bo'yicha dasturning kutilayotgan ish vaqti.

Ba'zi algoritmlar o'rtacha va eng yomon holatlar uchun aniq matematik formulalar ma'lum bo'lgan ma'noda yaxshi o'rganilgan. Bunday formulalar matematik xarakteristikalar bo'yicha ishlash vaqtini topish uchun dasturlarni sinchkovlik bilan o'rganish va keyin ularning matematik tahlilini o'tkazish orqali ishlab chiqiladi.

Ushbu turdagi tahlil uchun bir nechta muhim sabablar mavjud:
1. Yuqori darajadagi tilda yozilgan dasturlar mashina kodlariga tarjima qilinadi va u yoki bu operatorni bajarish uchun qancha vaqt ketishini tushunish qiyin bo'lishi mumkin.
2. Ko'pgina dasturlar kiritilgan ma'lumotlarga juda sezgir va ularning ishlashi ularga juda bog'liq bo'lishi mumkin. O'rtacha holat dastur qo'llaniladigan ma'lumotlar bilan bog'liq bo'lmagan matematik fantastika bo'lib chiqishi mumkin va eng yomon holat bo'lishi mumkin emas.

Saralashda eng yaxshi, o'rtacha va eng yomon holatlar katta rol o'ynaydi.
Saralash hisobi

O-murakkablik tahlili ko'plab amaliy dasturlarda keng tarqaldi. Shunga qaramay, uning cheklovlarini aniq tushunish kerak.

TO yondashuvning asosiy kamchiliklari quyidagilarni o'z ichiga oladi:
1) murakkab algoritmlar uchun O-baholarini olish, qoida tariqasida, juda ko'p vaqt talab qiladi yoki deyarli imkonsizdir;
2) ko'pincha "o'rtacha" murakkablikni aniqlash qiyin,
3) O-baholari algoritmlar orasidagi nozik farqlarni aks ettirish uchun juda qo'pol,
4) O-tahlil kichik hajmdagi ma'lumotlarni qayta ishlashda algoritmlarning harakatini tahlil qilish uchun juda kam ma'lumot beradi (yoki umuman bermaydi).

O-notatsiyasida murakkablikni aniqlash ahamiyatsiz emas. Xususan, ikkilik qidiruvning samaradorligi pastadirlarni joylashtirish chuqurligi bilan emas, balki har bir keyingi urinishni tanlash usuli bilan belgilanadi.

Yana bir qiyin qism - "o'rtacha holat" ni aniqlash. Algoritmning ishlash shartlarini bashorat qilishning iloji yo'qligi sababli buni qilish odatda juda qiyin. Ba'zan algoritm katta, murakkab dasturning bir qismi sifatida ishlatiladi. Ba'zan apparat va/yoki operatsion tizimning samaradorligi yoki kompilyatorning ba'zi komponentlari algoritmning murakkabligiga sezilarli ta'sir qiladi. Ko'pincha, bir xil algoritm turli xil ilovalarda ishlatilishi mumkin.

Algoritmning vaqt murakkabligini "o'rtacha" tahlil qilish bilan bog'liq qiyinchiliklar tufayli ko'pincha eng yomon va eng yaxshi holatlar uchun taxminlar bilan kifoyalanish kerak. Ushbu hisob-kitoblar asosan "o'rtacha" qiyinchilikning pastki va yuqori chegaralarini belgilaydi. Aslida, agar algoritmning murakkabligini "o'rtacha" tahlil qilishning iloji bo'lmasa, Merfi qonunlaridan biriga amal qilish kerak, unga ko'ra eng yomon holat uchun olingan baho "o'rtacha" murakkablikning yaxshi yaqinlashuvi bo'lib xizmat qilishi mumkin. ".

Ehtimol, O-funksiyalarining asosiy kamchiliklari ularning juda qo'polligidir. Agar A algoritmi qandaydir vazifani 0,001 * N s da bajarsa, uni B algoritmidan foydalangan holda hal qilish uchun 1000 * N s kerak bo'lsa, u holda B A dan million marta tezroq bo'ladi. Shunga qaramay, A va B bir xil vaqt murakkabligi O ga ega. (N).

Ushbu ma'ruzaning ko'p qismi algoritmlarning vaqt murakkabligini tahlil qilishga bag'ishlangan. Murakkablikning boshqa shakllari ham borki, ularni unutmaslik kerak: fazoviy va intellektual murakkablik.

Fazoviy murakkablik, dasturni bajarish uchun zarur bo'lgan xotira miqdori haqida avval aytib o'tilgan edi.

Algoritmning intellektual murakkabligini tahlil qilishda algoritmlarning tushunarliligi va ularni ishlab chiqishning murakkabligi tekshiriladi.

Murakkablikning barcha uchta shakli odatda o'zaro bog'liqdir. Odatda, yaxshi vaqtinchalik murakkablik hisobiga ega algoritmni ishlab chiqishda uning fazoviy va/yoki intellektual murakkabligidan voz kechish kerak. Misol uchun, tez tartiblash algoritmi namunaviy tartiblash algoritmidan sezilarli darajada tezroq. Saralash tezligini oshirish uchun to'lov saralash uchun zarur bo'lgan ko'proq xotirada ifodalanadi. Tez tartiblash uchun qo'shimcha xotiraga bo'lgan ehtiyoj bir nechta rekursiv qo'ng'iroqlar bilan bog'liq.

Quicksort, shuningdek, kiritish tartibidan ko'ra aqlliroq murakkabroq. Agar siz yuzlab odamlardan ob'ektlar ketma-ketligini saralashni so'rasangiz, ularning aksariyati namunaviy tartiblash algoritmidan foydalanadi. Ulardan birortasi ham tezkor saralashdan foydalanishi dargumon. Tez tartiblashning ko'proq intellektual va fazoviy murakkabligining sabablari aniq: algoritm rekursiv, uni tasvirlash ancha qiyin, algoritm oddiyroq tartiblash algoritmlariga qaraganda uzunroq (dastur matnini anglatadi).

Ko'pincha bir xil muammoni hal qilish uchun bir nechta algoritmlar ishlab chiqilishi mumkin. Shu munosabat bilan savol tug'iladi: algoritmlarning qaysi biri "yaxshiroq"?

Ko'pgina hollarda, "yaxshiroq", aftidan, xuddi shu kiritilgan ma'lumotlardan foydalangan holda, kamroq hisoblash resurslarini (xotira va vaqt) sarflaydigan muammoni hal qilishga keladigan algoritmdir. Bu, albatta, bo'sh fikr. Aniqroq fikr yuritish uchun biz bir nechta tushunchalarni kiritamiz.

Algoritmni hisoblash jarayoni - bu ba'zi kiritilgan ma'lumotlar uchun algoritmning bajarilishidan o'tgan bosqichlar ketma-ketligi.

Algoritmning o'zi va ushbu algoritm tomonidan yaratilgan hisoblash jarayoni o'rtasidagi farqni tushunish muhimdir. Birinchisi faqat tavsifi ikkinchi.

Algoritmning vaqt murakkabligi - ba'zi kiritilgan ma'lumotlar uchun algoritmning hisoblash jarayonini yakunlash uchun zarur bo'lgan vaqt \ (T \).

Amalga oshirish muddati aniq ijrochiga bog'liqligi aniq. Aytaylik, elektron kalkulyator va superkompyuter bir xil algoritmni turli vaqtlarda ishlatishi mumkin.

Biroq, \ (T \) vaqtni elementar harakatlar soni \ (k \) va elementar harakatning o'rtacha bajarilish vaqti \ (t \) bilan ifodalash mumkin:

Bundan tashqari, \ (k \) xususiyatdir eng algoritm, va \ (t \) - ijrochining xossasi.

Berilgan ijrochi uchun \ (t \) doimiy deb hisoblanishi mumkinligi sababli, odatda algoritmlarning murakkabligi doimiy koeffitsientgacha baholanadi. Boshqacha qilib aytganda, algoritmning murakkabligi taxmin qilinadi o'sish tartibi.

O'sish tartibi musbat aniq funksiya \ (g (x) \) o'sish tartibiga ega \ (f (x) \) (yozma \ (g (x) = \ mathcal (O) (f (x)) \)) agar \ (\ mavjud c> 0: \: \ forall x> x_0, \, g (x) \ leq c f (x) \).

Kirish ma'lumotlariga qarab, algoritm turli vaqtlarda ishlashi mumkin. Odatda baholanadi o'rtacha murakkablik va murakkablik eng yomoni... ga qaramlik ham mavjud miqdori ma'lumotlarni kiritish \ (n \). Odatda \ (n \) ning o'sish tartibi baholanadi.

Masalan, ma'lumotlarni o'qish va uni xotirada massiv sifatida saqlash murakkablikga ega bo'ladi \ (\ mathcal (O) (n) \) yoki chiziqli murakkablik, va matritsani ko'paytirish allaqachon kub\ (\ matematik (O) (n ^ 3) \).

Algoritmning vaqt murakkabligidan tashqari, u ham muhimdir fazoviy algoritmning murakkabligi.

Algoritmning fazoviy murakkabligi sondir qo'shimcha xotira \ (S \), algoritm ishlashi uchun talab qilinadi. Kirish ma'lumotlarini saqlash uchun zarur bo'lgan xotira \ (D \) \ (S \) tarkibiga kiritilmagan.

\ (S \) odatda aktuatorga ham bog'liq. Misol uchun, agar ikkita aktuator mos ravishda 4 va 8 baytli butun sonlarni qo'llab-quvvatlasa, u holda 8 baytli butun sonlar uchun algoritmning fazoviy murakkabligi 4 baytli butun sonlarga qaraganda ikki baravar katta bo'ladi. Shuning uchun fazoviy murakkablik bir xil o'sish tartibida baholanadi.

Algoritm murakkabligi sinflari

Aniq qiyinchilik sinflari: Bular xuddi shunday qiyinchilikka ega toifalar.

Quyidagi asosiy qiyinchilik sinflari ajratiladi:

DTIME Tyuring mashinasi muammoning yechimini cheklangan vaqt ichida (qadamlar soni) topadi. Algoritmning asimptotikasi ko'pincha belgilanadi, shuning uchun aytaylik, agar ish vaqtining o'sish tartibi \ (T (n) = \ mathcal (O) (f (n)) \), keyin \ (DTIME (f) bo'lsa. (n)) \) ko'rsatilgan. P Turing mashinasi muammoning yechimini polinom vaqtida (qadamlar soni) topadi, ya'ni. \ (T (n) = \ matematik (O) (n ^ k) \), bu erda \ (k \ in \ mathbb (N) \). \ (P = DTIME (n ^ k) \) EXPTIME Tyuring mashinasi muammoning yechimini eksponensial vaqtda (qadamlar soni) topadi, ya'ni. \ (T (n) = \ matematik (O) (2 ^ (n ^ k)) \), bu erda \ (k \ in \ mathbb (N) \). \ (EXPTIME = DTIME (2 ^ (n ^ k)) \). DSPACE Turing mashinasi cheklangan miqdordagi qo'shimcha xotira (hujayralar) yordamida muammoning yechimini topadi. Algoritmning asimptotikasi ko'pincha belgilanadi, shuning uchun aytaylik, agar xotira iste'molining o'sish tartibi \ (S (n) = \ mathcal (O) (f (n)) \), keyin \ (DSPACE (f ()) n)) \) ko'rsatilgan. L Tyuring mashinasi logarifmik fazoviy murakkablikdagi muammoning yechimini topadi, ya'ni. \ (S (n) = \ matematik (O) (\ log n) \)... \ (L = DSPACE (\ log n) \). PSPACE Tyuring mashinasi polinom fazoviy murakkablikdagi masalaning yechimini topadi, ya'ni \ (S (n) = \ mathcal (O) (n ^ k) \), bu erda \ (k \ in \ mathbb (N) \ ). \ (PSPACE = DSPACE (n ^ k) \). EXPSPACE Turing mashinasi eksponensial fazoviy murakkablikdagi muammoning yechimini topadi, ya'ni. \ (S (n) = \ matematik (O) (2 ^ (n ^ k)) \), bu erda \ (k \ in \ mathbb (N) \). \ (EXPSPACE = DSPACE (2 ^ (n ^ k)) \).

Bundan tashqari, kontseptsiyada ishlaydigan nazariy murakkablik sinflari mavjud aniqlanmagan Tyuring mashinalari (TMT). Ularning ta'riflari yuqoridagilarga to'g'ri keladi, Tyuring mashinasini NMT bilan almashtirish va nomlar N prefiksiga ega (masalan, NP), NTIME va NSPACE bundan mustasno, bu erda D N bilan almashtiriladi.

NMT - bu sof nazariy konstruktsiya bo'lib, u o'zining ishlash tamoyillari bo'yicha MTga o'xshaydi, farqi bilan har bir shtat uchun mavjud bo'lishi mumkin. bir nechta mumkin bo'lgan harakatlar. Shu bilan birga, NMT har doim mumkin bo'lgan harakatlardan minimal mumkin bo'lgan qadamlar sonida yechimga olib keladiganini tanlaydi. Xuddi shunday, HMT hisoblaydi hammasidan novdalar va minimal mumkin bo'lgan qadamlar sonida yechimga olib keladigan filialni tanlaydi.

Ba'zida kvant kompyuterlari HMT ning qo'llanilishi deb eshitiladi. Ba'zi hollarda bu to'g'ri ko'rinishi mumkin bo'lsa-da, umuman olganda, HMT kvant kompyuteriga qaraganda kuchliroq tizimdir.

Ma'lumki \ (P \ subseteq NP \ subseteq PSPACE \ subseteq EXPTIME \ subseteq NEXPTIME \ subseteq EXPSPACE \)

Shuningdek, \ (P \ subsetneq EXPTIME \), \ (NP \ subsetneq NEXPTIME \), \ (PSPACE \ subsetneq EXPSPACE \)

Bundan tashqari, ma'lumki, agar \ (P = NP \), keyin \ (EXPTIME = NEXPTIME \).

P va NP tengligi masalasi zamonaviy kompyuter fanining hal qilinmagan asosiy savollaridan biridir.

Algoritmga misollar

Bu erda oddiy algoritmlarning ba'zi misollari va ularning murakkabligini ko'rib chiqing.

Koʻrsatkich koʻtarish

Ushbu algoritm qadimgi Hindistonda bizning eramizdan oldin tasvirlangan va haqiqiy sonning \ (n \) tabiiy kuchini \ (x \) hisoblash uchun ishlatiladi.

1. \ (n \) ni ikkilik tizimda yozing
2. Ushbu yozuvdagi 1 ning har birini bir juft KX harfi bilan, har bir 0 ni esa K harfi bilan almashtiring
3. Eng chapdagi KX juftligini kesib tashlang
4. Olingan satrni chapdan o'ngga o'qish, K harfi bilan uchrashish, natijani kvadratga tushirish va X harfini uchratish, natijani x ga ko'paytiring. Boshida natija x ga teng.

Bu algoritmda biz ko'paytirish amallari soni ikkilik ko'rinishdagi raqamlar soniga eng yaxshi \ (n \) va eng yomoni \ (2 (n-1) \) ga teng. Vaqt murakkabligi baribir.

Algoritmni samarali amalga oshirishda qo'shimcha xotira amalda talab qilinmaydi va u kiritilgan ma'lumotlarga bog'liq emas, shuning uchun fazoviy murakkablik \ (S (n) = \ matematik (O) (1) \) ga teng.

Shuni ta'kidlash kerakki, yanada samarali algoritmlar mavjud. Biroq, \ (\ mathcal (O) (n) \) ko'paytirish operatsiyalarini talab qiladigan "sodda" amalga oshirish bilan solishtirganda, bu algoritm nisbatan samarali.

Butun sonlarni ko‘paytirish

Ushbu ko'paytirish algoritmi ba'zan rus yoki dehqon deb ataladi, garchi u Qadimgi Misrda ham ma'lum bo'lgan.

Birinchi omil ketma-ket ikkiga ko'paytiriladi, ikkinchisi esa to'liq 2 ga bo'linadi. Natijalar ikkinchisi 1 bo'lguncha ikkita ustunga yoziladi.

Ko'paytirish natijasi birinchi ustundagi raqamlarning yig'indisi, ikkinchi ustundagi toq raqamlarning qarama-qarshiligi.

Butun sonlarni bo'lish va 2 ga ko'paytirishni siljish yo'li bilan bajarish mumkin bo'lganligi sababli, bu algoritm \ (2 \ log_2 n \) siljish amallarini beradi, bu erda \ (n \) ikkita sondan kichikroqdir. Eng yomon holatda, \ (\ log_2 n - 1 \) qo'shish operatsiyalari ham olinadi. Qanday bo'lmasin, vaqtning murakkabligi \ (T (n) = \ matematik (O) (\ log n) \).

Algoritmni samarali amalga oshirish uchun qo'shimcha xotira deyarli talab qilinmaydi va u kiritilgan ma'lumotlarga bog'liq emas, shuning uchun \ (S (n) = \ mathcal (O) (1) \)

Yana shuni ta'kidlash kerakki, yanada samarali algoritmlar mavjud. Biroq, \ (\ mathcal (O) (n) \) qo'shish operatsiyalarini talab qiladigan "sodda" amalga oshirish bilan solishtirganda, bu algoritm nisbatan samaralidir.

Misol

23 ni 43 ga ko'paytiring.

Ikkinchi omil sifatida 23 ni olaylik.

43	23	g'alati
86	11	g'alati
172	5	g'alati
344	2
688	1	g'alati

Natija \ (43 + 86 + 172 + 688 = 989 \)

Bizda 10 ta smenali operatsiya va 4 ta qo'shimcha operatsiya mavjud. Malumot uchun, \ (\ log_2 (23) \ taxminan 4,52 \).

Algoritmning murakkabligini aniqlash

Asimptotik tahlilda olingan murakkablik funksiyasining bahosi algoritmning murakkabligi deyiladi.

Shuni yodda tutish kerakki, algoritmning murakkabligi bo'yicha bir nechta taxminlar mavjud.

Murakkablik funktsiyasining asimptotik xatti-harakati operatsion murakkablikdir. Unga qo'shimcha ravishda siz quyidagi qiyinchiliklar turlarini belgilashingiz mumkin.

Vaqtinchalik murakkablik - uzunlikdagi kirish ma'lumotlari bo'yicha algoritmning ishlash vaqtining asimptotik bahosi P. Shubhasiz, hisoblash protseduralarini parallellashtirish mavjud bo'lmaganda, algoritmning ishlash vaqti bajarilgan operatsiyalar soni bilan yagona aniqlanadi. Operatsiyalarning davomiyligini ifodalovchi doimiy koeffitsientlar vaqt murakkabligi tartibiga ta'sir qilmaydi, shuning uchun operatsion va vaqt murakkabligi uchun formulalar ko'pincha bir-biriga to'g'ri keladi.

Kapasitiv murakkablik - uzunlikdagi kirish ma'lumotlari bo'yicha algoritmni bajarishda bir vaqtning o'zida mavjud bo'lgan skalerlar sonining asimptotik bahosi P.

Strukturaviy murakkablik - algoritmdagi boshqaruv tuzilmalari sonining xarakteristikasi va ularning interpozitsiyasining o'ziga xosligi.

Kognitiv murakkablik - amaliy sohalardagi mutaxassislar tomonidan tushunish uchun algoritm mavjudligining xarakteristikasi.

Asimptotiklarning turlari va belgilanishi

Algoritmlarning asimptotik tahlilida matematik asimptotik tahlilning yozuvidan foydalanish odatiy holdir. Bunday holda, algoritmlarning murakkabligining uchta bahosi (asimptotikasi) ko'rib chiqiladi, ular quyidagicha belgilanadi:

• 1) / (i) = O ^ (n))- murakkablik funksiyasining asimptotik aniq bahosi / («), yoki algoritmning operatsion murakkabligi;
• 2) /(n) = 0 (§ (n)) - murakkablik funktsiyasi uchun asimptotik keskin yuqori chegara / ( P);
• 3) / (n) =? 2 (# (n)) murakkablik funksiyasi uchun asimptotik aniq past bahodir / ( P).

Belgilash o'rniga C1 ^ (n)) juda tez-tez "o" harfi bilan oddiyroq o (^ (")) kichik kursivda ishlatiladi.

Formulalarning semantikasini misol orqali tushuntirib beraylik: agar u / (i) = 0 (^ 2 (l)) deb yozilsa, BU funksiyani bildiradi. g (n) = og2 (n) murakkablik funksiyasi uchun asimptotik aniq bahodir / (a). Aslida, bayonot shaklida ikki pozitsiyali ta'rif mavjud:

Agar f (n)= @ (jurnal 2 (")),

mo g (n)= log 2 (l) - f (n) uchun asimptotik keskin taxmin.

E'tibor bering, doimiy omil algoritmning murakkablik tartibiga ta'sir qilmaydi, shuning uchun logarifmik murakkablikni ko'rsatishda logarifm asosi o'tkazib yuboriladi va ular shunchaki / (n) = @ (log (n)) ni yozib, shuni nazarda tutadi. logarifm birdan katta ixtiyoriy asosga ega.

Asimptotiklarning rasmiy ta'riflari

Mehnat intensivligi funksiyasining asimptotik keskin bahosi Bilan, Bilan 2, n 0 shunday bo'lsinki, n> n 0 uchun f (n) funksiyasi o'zgarmas koeffitsientlargacha funksiyadan farq qilmaydi. g ( l), keyin funksiya g (n) f (x) funktsiyasi uchun asimptotik o'tkir taxmin deyiladi.

• 3 s], s 2 e F, x bilan > 0, 2> bilan 0:
  • (3 l 0 e K, l 0> 0: (/ l e K, l> l 0: 0 g (n) / (l) = 0 (? (L)),

bu yerda 9 ^, N mos ravishda barcha haqiqiy va natural sonlar to‘plamidir.

Murakkablik funksiyasi uchun asimptotik keskin yuqori chegara og'zaki ravishda quyidagicha aniqlanadi: agar ijobiy raqamlar bo'lsa Bilan va n 0 shunday bo'lsinki, n> n 0 uchun f (n) funksiya funktsiyadan tezroq o'smaydi. g (n) doimiy koeffitsient c gacha, keyin funksiya g (n) funksiya uchun asimptotik keskin yuqori chegara deyiladi Ap).

Ta'rifning aniqroq rasmiy belgisi quyidagicha:

• 3 Bilan e % s> 0:
  • (3 l 0 e X, l 0> 0: (/ l e K, l> l 0: 0 s? # (L))) 0 (g (n))

Murakkablik funktsiyasi uchun asimptotik keskin pastki chegara og'zaki ravishda quyidagicha aniqlanadi: agar ijobiy raqamlar bo'lsa Bilan va n 0 shunday bo'lsinki, n> n 0 uchun f (n) funksiya funksiyadan sekin o'smaydi. g (n) doimiy omilgacha Bilan, u holda funksiya?(l) funksiya uchun asimptotik keskin pastki chegara deyiladi

Ta'rifning aniqroq rasmiy belgisi quyidagicha:

• 3 Bilan e 9 ^, Bilan > 0:
  • (3 i 0 e X, i 0> 0: (/ i e K, i > men 0: 0 s? g (n)

/(men) = 0. ^ (N))

Quyidagilarga e'tibor bering:

• 1) asimptotikaning rasmiy ta'riflarida ko'rsatilgan tengsizliklar, umumiy holda, bir emas, balki ba'zi funktsiyalar to'plamini, ko'pincha cheksiz atamalar to'plamini qondirishi mumkin, shuning uchun konstruktsiyalar Q (g (n)), 0 ^ (n)) va 0. ^ (N)) ramziy qiladi ko'p funktsiyalar u bilan mehnat intensivligining tekshirilgan funktsiyasi f (i) solishtiriladi; shundan kelib chiqqan holda, f (x) = 0 (q (x)), f (f0 = 0 (q max (n)), d) = q 2 (q mn (x)) ko'rinishdagi asimptotikaning yozuvida. ) "=" belgisi o'rniga "e" belgisidan foydalanish oqilonaroq bo'ladi;
• 2) konstruksiyalar (d ^ (n)), 0 ^ (n)) va ? 1 ^ (n)), Ba'zi miqdorlar uchun belgi sifatida qo'llaniladigan so'zlar mos ravishda quyidagicha o'qilishi kerak: mos keladigan har qanday funktsiya tezroq o'smaydi va sekinroq o'smaydi. g (n).

Asimptotiklarning tasodif va farqi

Keling, quyidagi faktga e'tibor qarataylik: f (i) = 0 (? (I)) bahosi f (i) uchun ham yuqori, ham pastki chegaralarni o'rnatadi, chunki uning ta'rifi munosabatning haqiqiyligini taxmin qiladi. c g (n)

Asimptotikaning quyidagi xossasi juda aniq: agar taxmin ph (n) = © ^ (n)) mavjud bo'lsa, tengliklar / ( P) = 0 (^ (i)) va f (i) =? 2 (# (i)), ya'ni. mehnat zichligining yuqori va pastki baholari bir-biriga to'g'ri keladi; agar f (i) = 0 (? max (i)) va ph (n) = C1 ^ mt (n)), va g max (n) fg m Ln (i), keyin hech qanday funktsiya yo'q g (n), shunday qilib / (i) = 0 (? (i)).

Mehnat zichligining yuqori va pastki baholarining mos kelishi quyidagi hollarda mumkin:

• 1) kirish uzunligining barcha qiymatlari uchun murakkablik funktsiyasi deterministik (tasodifiy bo'lmagan) funktsiyadir, ya'ni. bajarilgan operatsiyalar soni dastlabki ma'lumotlar qiymatlarining o'ziga xos xususiyatlariga bog'liq emas; bunday, masalan, IZ parchalanish usuli bilan chiziqli algebraik tenglamalar tizimlarini yechish algoritmidagi noma'lum miqdorlar soniga ko'paytirish va bo'lish amallari sonining bog'liqlik funktsiyalari;
• 2) mehnat intensivligi funktsiyasi tasodifiy funktsiyadir, ya'ni. bajarilgan operatsiyalar soni dastlabki ma'lumotlarning o'ziga xos xususiyatlariga va (yoki) ularni olish tartibiga bog'liq va siz / t | n (i), / max (i) funktsiyalarini belgilashingiz mumkin, minimal va maksimal sonni tavsiflaydi. ma'lum bir kirish uzunligi i uchun algoritm ijrochisi tomonidan bajariladigan amallar, ammo bu funktsiyalarning ikkalasi ham bir xil dominantlarga ega - masalan, ular bir xil tartibdagi ko'phadlardir.

Operatsion murakkablik tartibini baholashda uchta muhim qoidani yodda tutish kerak:

• 1) murakkablik tartibini aniqlash uchun doimiy omillar muhim emas, ya'ni. 0 (k? g (n)) = 0 (g ("));
• 2) ikkita funktsiya hosilasining murakkablik tartibi ularning murakkabligi mahsulotiga teng, chunki tenglik to'g'ri:
• 0 (gl (i) §2(i)) = 0 (? | (i)) 0 (# 2 (i));
• 3) funksiyalar yig'indisining murakkablik tartibi atamalar dominantining tartibiga teng, masalan: 0 (i e) + n 2 + n) = 0 (i 5).

Yuqoridagi qoidalarda faqat bitta asimptotikning belgisi 0 (») ishlatiladi, ammo ular barcha asimptotik baholar uchun amal qiladi - va 0( ) , va &.{ ).

Elementar funktsiyalar to'plamida siz funktsional ustunlik ro'yxatini belgilashingiz mumkin: agar o'zgaruvchi bo'lsa, a, b - sonli konstantalarda quyidagi gaplar to‘g‘ri bo‘ladi: I “Men hukmronman!; Men! hukmronman a "; a" ustunlik qiladi Zj "agar a> b a n hukmronlik qiladi P b agar a har qanday uchun > 1 b e 9? ; n a a / agar hukmronlik qiladi a> b i log q (i) bo'lsa hukmronlik qiladi a > 1.

O'rtacha mehnat intensivligini baholash

Amalda, qayta Ba'zi hisob-kitoblarda M ning murakkabligini matematik kutishning f (n) bahosi katta qiziqish uyg'otadi, chunki aksariyat hollarda f (n) tasodifiy funktsiyadir. Biroq, tasodifiy f (i) bilan algoritmlarni eksperimental o'rganish jarayonida qo'shimcha muammo tug'iladi - M ni ishonchli baholash uchun testlar sonini tanlash. Taklif etilayotgan yechim / (i) ni taxmin qilish uchun beta taqsimotidan foydalanishga asoslangan. Bu juda konstruktiv va ko'p qirrali texnika. Biroq, zamonaviy sharoitda, kompyuterning unumdorligi etarlicha yuqori bo'lsa, ko'p hollarda qiymatlarning joriy o'zgaruvchanligini nazorat qilish asosida testlar hajmini tanlashning oddiyroq usulini qo'llash mumkin. f (n) - qiymatlar baholarning o'zgaruvchanligi belgilangan xatolikdan kam bo'lgunga qadar baholanadi.

Algoritmning operatsion murakkabligini baholash

Algoritmning murakkabligini uning boshqaruv tuzilmalarini tahlil qilish asosida aniqlash mumkin. Loopsiz va rekursiv chaqiruvlarsiz algoritmlar doimiy murakkablikka ega. Shuning uchun algoritmning murakkabligini aniqlash asosan tsikllar va rekursiv chaqiruvlarni tahlil qilishga qisqartiriladi.

O'chirish algoritmini ko'rib chiqing Kimga o'lcham massividan th element P dan harakatlanuvchi massiv elementlaridan iborat (k + 1) dan P-massiv boshiga qaytish va elementlar sonini kamaytirish P birlik uchun. Massivni qayta ishlash siklining murakkabligi Oh (p-k) pastadir tanasi (harakat qilish operatsiyasi) bajarilganligi sababli Kompyuter marta, va pastadir tanasining murakkabligi 0 (1), ya'ni. doimiydir.

Ko'rib chiqilayotgan misolda murakkablik asimptotik 0 (") bilan tavsiflanadi, chunki bu algoritmda bajariladigan operatsiyalar soni ma'lumotlar qiymatlarining o'ziga xos xususiyatlariga bog'liq emas. Murakkablik funktsiyasi deterministik bo'lib, asimptotikaning barcha turlari bir-biriga to'g'ri keladi: f (n) = Q (n-k), f (n) = 0 (n-k) va f (n) = Q (n-dan). Bu fakt © () belgisi bilan tasdiqlanadi. 0 (*) va/yoki 2 (*) dan faqat ushbu asimptotiklar boshqacha bo'lsa foydalanish kerak.

Loop turi (for, while, takrorlash) murakkablikka ta'sir qilmaydi. Agar bir sikl boshqasiga o'rnatilgan bo'lsa va ikkala tsikl ham bir xil o'zgaruvchining o'lchamiga bog'liq bo'lsa, unda butun qurilish kvadratik murakkablik bilan tavsiflanadi. Takroriy uyalar qiyinchilikni oshiradigan asosiy omil hisoblanadi. Misol tariqasida, biz o'lchamdagi massiv uchun taniqli qidirish va saralash algoritmlarining murakkabligini keltiramiz. P:

• ketma-ket qidiruvda taqqoslash operatsiyalari soni: 0 (i);
• Ikkilik qidiruvda taqqoslash operatsiyalari soni: 0 (log 2 P);
• oddiy almashuv usulida taqqoslash operatsiyalari soni (qabariqli tartiblash): 0 (i 2);
• pufakchali tartibdagi almashtirish operatsiyalari soni: 0 (n 2);

E'tibor bering, oddiy almashish usulida taqqoslash operatsiyalari soni asimptotikaga ega 0 (n 2) va almashtirish operatsiyalari soni ikki xil asimptotikaga ega 0 (n 2) va? 2 (0), chunki taqqoslashlar soni saralangan ma'lumotlar qiymatlarining o'ziga xos xususiyatlariga bog'liq emas, almashtirishlar soni esa ushbu o'ziga xoslik bilan aniq belgilanadi. O'zgartirishlar umuman amalga oshirilmasligi mumkin - agar ma'lumotlar qatori dastlab to'g'ri tartiblangan bo'lsa yoki almashtirishlar soni maksimal bo'lishi mumkin - taxminan P 2, - agar tartiblangan massiv dastlab teskari yo'nalishda tartiblangan bo'lsa.

Funktsiya nomi g (n) asimptotikada f (n) = @ (t (n)) va f (a) = 0 (g (n)) algoritmni tavsiflash uchun murakkablik funksiyasi / (") ishlatiladi. Shunday qilib, polinom, eksponensial, logarifmik va hokazo murakkablik algoritmlari haqida gapiriladi.