Salom! Bugungi ma'ruzamiz qolganlardan biroz farq qiladi. Bu faqat bilvosita Java bilan bog'liqligi bilan farq qiladi. Biroq, bu mavzu har bir dasturchi uchun juda muhimdir. Biz gaplashamiz algoritmlar. Algoritm nima? Gapirmoqda oddiy tilda, bu istalgan natijaga erishish uchun bajarilishi kerak bo'lgan muayyan harakatlar ketma-ketligi. Biz kundalik hayotda ko'pincha algoritmlardan foydalanamiz. Masalan, har kuni ertalab siz bir vazifaga duch kelasiz: maktabga yoki ishga kelish va shu bilan birga:

• Kiyingan
• Toza
• Yaxshi ovqatlangan

Qaysi algoritm bu natijaga erishishga imkon beradimi?

1. Budilnikda uyg'onish.
2. Dush qabul qiling, yuzingizni yuving.
3. Nonushta tayyorlang, qahva / choy tayyorlang.
4. Ovqatlang.
5. Kechqurun kiyimingizni dazmollamagan bo'lsangiz, dazmollang.
6. Kiyin.
7. Uyni tark et.

Ushbu harakatlar ketma-ketligi, albatta, kerakli natijaga erishishga imkon beradi. Dasturlashda bizning ishimizning asosiy maqsadi doimiy ravishda muammolarni hal qilishdir. Ushbu vazifalarning muhim qismi allaqachon ma'lum bo'lgan algoritmlar yordamida bajarilishi mumkin. Masalan, siz quyidagi vazifaga duch kelasiz: massivdagi 100 ta nomdan iborat roʻyxatni tartiblash. Bu muammo juda oddiy, ammo uni hal qilish mumkin turli yo'llar bilan. Mana bitta yechim: Nomlarni alifbo tartibida saralash algoritmi:

1. Internetda sotib oling yoki yuklab oling "Ruscha shaxsiy ismlar lug'ati" 1966 yil nashri.
2. Ushbu lug'atda ro'yxatimizdagi barcha nomlarni toping.
3. Nomi lug'atning qaysi sahifasida ekanligini qog'ozga yozing.
4. Bir qog'ozdagi eslatmalardan foydalanib, ismlarni tartibda qo'ying.

Bunday harakatlar ketma-ketligi muammomizni hal qilishga imkon beradimi? Ha, bu butunlay ruxsat beradi. Bu yechim bo'ladimi samarali? Qiyin. Bu erda biz algoritmlarning yana bir muhim xususiyatiga keldik - ularning samaradorlik. Muammoni turli yo'llar bilan hal qilish mumkin. Ammo dasturlashda ham, kundalik hayotda ham biz eng samarali bo'ladigan usulni tanlaymiz. Agar sizning vazifangiz sariyog 'bilan sendvich tayyorlash bo'lsa, siz, albatta, bug'doy ekish va sigirni sog'ish bilan boshlashingiz mumkin. Lekin shunday bo'ladi samarasiz yechim - bu juda uzoq vaqt talab etadi va juda ko'p pul talab qiladi. Oddiy muammoni hal qilish uchun siz shunchaki non va sariyog' sotib olishingiz mumkin. Va bug'doy va sigir bilan algoritm, garchi bu muammoni hal qilishga imkon bersa ham, uni amalda qo'llash uchun juda murakkab. Dasturlashda algoritmlarning murakkabligini baholash uchun maxsus belgi yaratildi Big-O (“katta O”). Big-O algoritmning bajarilish vaqti unga berilgan ma'lumotlarga qanchalik bog'liqligini taxmin qilish imkonini beradi.. Keling, eng oddiy misolni ko'rib chiqaylik - ma'lumotlar uzatish. Tasavvur qiling-a, ba'zi ma'lumotlarni fayl shaklida uzoq masofaga (masalan, 5000 kilometr) uzatishingiz kerak. Qaysi algoritm eng samarali bo'ladi? Bu uning ishlashi kerak bo'lgan ma'lumotlarga bog'liq. Misol uchun, bizda 10 megabayt hajmdagi audio fayl mavjud.
Bunday holda, faylni Internet orqali uzatish eng samarali algoritm bo'ladi. Maksimal bir necha daqiqa davom etadi! Shunday qilib, keling, algoritmimizni yana bir bor aytaylik: "Agar siz 5000 kilometr masofaga ma'lumotlarni fayllar shaklida uzatishingiz kerak bo'lsa, Internet orqali ma'lumotlarni uzatishdan foydalanishingiz kerak." Ajoyib. Endi uni tahlil qilaylik. Bu bizning muammomizni hal qiladimi? Umuman olganda, ha, uni butunlay hal qiladi. Ammo uning murakkabligi haqida nima deya olasiz? Hmm, endi bu erda narsalar qiziq bo'ladi. Gap shundaki, bizning algoritmimiz ko'p jihatdan kiruvchi ma'lumotlarga, ya'ni fayllar hajmiga bog'liq. Endi bizda 10 megabayt bor va hamma narsa yaxshi. Agar 500 megabaytni uzatishimiz kerak bo'lsa-chi? 20 gigabayt? 500 terabayt? 30 petabayt? Bizning algoritmimiz ishlashni to'xtatadimi? Yo'q, bu ma'lumotlarning barchasini hali ham uzatish mumkin. Bajarish uchun ko'proq vaqt kerakmi? Ha, bo'ladi! Endi biz algoritmimizning muhim xususiyatini bilamiz: O'tkazilishi kerak bo'lgan ma'lumotlarning hajmi qanchalik katta bo'lsa, algoritmni bajarish uchun shuncha ko'p vaqt kerak bo'ladi.. Ammo biz bu munosabat qanday ko'rinishini (ma'lumotlarning hajmi va uni uzatish vaqti o'rtasida) aniqroq tushunishni istaymiz. Bizning holatda, algoritmning murakkabligi bo'ladi chiziqli. "Chiziqli" ma'lumotlar hajmi oshgani sayin, uni uzatish vaqti taxminan mutanosib ravishda oshadi. Agar ma'lumotlar 2 barobar ko'p bo'lsa va uni uzatish uchun 2 baravar ko'proq vaqt kerak bo'ladi. Agar 10 barobar ko'p ma'lumot bo'lsa, uzatish vaqti 10 barobar ortadi. Big-O notatsiyasidan foydalanib, bizning algoritmimizning murakkabligi bilan berilgan O(N). Ushbu belgi kelajakda foydalanish uchun eng yaxshi esda qoladi - u har doim chiziqli murakkablikdagi algoritmlar uchun ishlatiladi. E'tibor bering: biz bu erda turli xil "o'zgaruvchan" narsalar haqida umuman gapirmayapmiz: Internet tezligi, kompyuterimizning kuchi va boshqalar. Algoritmning murakkabligini baholashda buning ma'nosi yo'q - baribir biz uni nazorat qila olmaymiz. Big-O algoritmning o'zini, qanday bo'lishidan qat'i nazar, baholaydi. muhit” unda u ishlashi kerak bo'ladi. Keling, misolimiz bilan davom etaylik. Aytaylik, oxir-oqibat uzatilishi kerak bo'lgan fayllar hajmi 800 terabayt ekanligi ma'lum bo'ldi. Agar biz ularni internet orqali uzatsak, muammo, albatta, hal bo'ladi. Faqat bitta muammo bor: ko'pchiligimiz uyimizda foydalanadigan standart zamonaviy havola (sekundiga 100 megabit) orqali uzatish taxminan 708 kun davom etadi. Taxminan 2 yil! :O Shunday qilib, bizning algoritmimiz bu erda mos emas. Bizga boshqa yechim kerak! To'satdan bizga IT giganti Amazon yordamga keladi! Uning Amazon Snowmobile xizmati sizga katta hajmdagi ma'lumotlarni mobil xotira bloklariga yuklash va yuk mashinasida kerakli manzilga etkazish imkonini beradi!
Shunday qilib, bizda yangi algoritm bor! "Agar siz 5000 kilometr masofaga ma'lumotni fayllar ko'rinishida uzatishingiz kerak bo'lsa va jarayon Internet orqali uzatilganda 14 kundan ortiq davom etsa, siz Amazon yuk mashinasi transportidan foydalanishingiz kerak." Bu erda 14 kunlik ko'rsatkich tasodifiy tanlangan: aytaylik, bu biz ko'tara oladigan maksimal muddat. Keling, algoritmimizni tahlil qilaylik. Tezlik haqida nima deyish mumkin? Yuk mashinasi atigi 50 km/soat tezlikda yursa ham, u atigi 100 soatda 5000 kilometrni bosib o'tadi. Bu to'rt kundan sal ko'proq! Bu Internetni uzatish variantidan ancha yaxshi. Ushbu algoritmning murakkabligi haqida nima deyish mumkin? U ham chiziqli bo'ladimi, O (N)? Yo'q, bo'lmaydi. Axir, yuk mashinasi uni qancha yuklaganingizga ahamiyat bermaydi - u baribir taxminan bir xil tezlikda harakatlanadi va o'z vaqtida yetib boradi. Bizda 800 terabayt yoki 10 baravar ko'p ma'lumot bormi, yuk mashinasi u erga 5 kun ichida etib boradi. Boshqacha qilib aytganda, yuk mashinasi orqali ma'lumotlarni etkazib berish algoritmi doimiy qiyinchilik. "Doimiy" algoritmga uzatilgan ma'lumotlarga bog'liq emasligini anglatadi. Yuk mashinasiga 1 Gb hajmli flesh-disk qo'ying, u 5 kun ichida keladi. U erda 800 terabayt ma'lumotga ega disklarni qo'ying va u 5 kun ichida keladi. Big-O dan foydalanganda doimiy murakkablik sifatida belgilanadi O(1). Biz uchrashganimizdan beri O(N) Va O(1), endi ko'proq "dasturchi" misollarini ko'rib chiqaylik :) Aytaylik, sizga 100 ta raqamdan iborat massiv berilgan va vazifa ularning har birini konsolga chiqarishdir. Bu vazifani bajaradigan muntazam for siklini yozasiz int numbers = new int [100]; // ..massivni raqamlar bilan to'ldiring for (int i: raqamlar) ( System. out. println (i) ; ) Yozilgan algoritmning murakkabligi nimadan iborat? Chiziqli, O(N). Dastur bajarishi kerak bo'lgan harakatlar soni unga qancha raqam kiritilganiga bog'liq. Agar massivda 100 ta raqam bo'lsa, 100 ta amal (ekrandagi chiqishlar) bo'ladi, agar massivda 10 000 ta raqam bo'lsa, 10 000 ta amalni bajarish kerak bo'ladi. Bizning algoritmimizni yaxshilash mumkinmi? Yo'q. Har qanday holatda ham qilishimiz kerak N massivdan o'tadi va konsolga N ta chiqishni bajaring. Keling, yana bir misolni ko'rib chiqaylik. < Integer> public static void main(String args) (LinkedList< >raqamlar = yangi LinkedList (); raqamlar. qo'shish (0, 20202); raqamlar. qo'shish (0, 123); raqamlar. qo'shish (0, 8283);

) Bizda bo'sh LinkedList bor, unga biz ba'zi raqamlarni kiritamiz. Bizning misolimizdagi LinkedList-ga bitta raqamni kiritish algoritmining murakkabligini va bu ro'yxatdagi elementlar soniga qanday bog'liqligini taxmin qilishimiz kerak. Javob bo'ladi

O(1) - doimiy murakkablik. Nega? E'tibor bering: har safar ro'yxatning boshiga raqam kiritamiz. Bundan tashqari, siz eslayotganingizdek, LinkedList-ga raqam kiritganingizda, elementlar hech qayerga siljimaydi - havolalar qayta aniqlanadi (agar siz to'satdan LinkedList qanday ishlashini unutib qo'ysangiz, biznikidan biriga qarang). Agar hozir ro'yxatimizda birinchi raqam x raqami bo'lsa va biz ro'yxatning boshiga y raqamini qo'shsak, faqat x kerak bo'ladi. oldingi = y; y. oldingi = null; topilgan bo'lsa, qidiruv to'xtatilishi kerak va konsolda "kerakli raqam topildi!" yozuvi ko'rsatilishi kerak. Uning massivdagi indeksi = ....” Bunday muammoni qanday hal qilgan bo'lardingiz? Bu erda yechim aniq: siz birinchi (yoki oxirgi) dan boshlab massiv elementlarini birma-bir takrorlashingiz va joriy raqam kerakli raqamga mos kelishini tekshirishingiz kerak. Shunga ko'ra, harakatlar soni to'g'ridan-to'g'ri massivdagi elementlar soniga bog'liq. Agar bizda 100 ta raqam bo'lsa, biz 100 marta keyingi elementga o'tishimiz va raqamni 100 marta tekshirishimiz kerak. Agar 1000 ta raqam bo'lsa, unda 1000 ta tekshirish bosqichi bo'ladi, bu aniq chiziqli murakkablik. O(N). Endi biz misolimizga bitta tushuntirish qo'shamiz: raqamni topishingiz kerak bo'lgan massiv o'sish tartibida tartiblangan. Bu bizning vazifamiz uchun biror narsani o'zgartiradimi? Biz hali ham qo'pol kuch bilan kerakli raqamni qidirishimiz mumkin. Ammo buning o'rniga biz taniqli narsalarni ishlatishimiz mumkin algoritm ikkilik qidiruv .
Rasmning yuqori qatorida biz tartiblangan massivni ko'ramiz. Unda biz 23 raqamini topishimiz kerak. Raqamlar ustida takrorlash o'rniga, biz oddiygina massivni 2 qismga bo'lamiz va massivdagi o'rtacha sonni tekshiramiz. Biz 4 katakda joylashgan raqamni topamiz va uni tekshiramiz (rasmdagi ikkinchi qator). Bu raqam 16, biz esa 23 ni qidiramiz. Hozirgi raqam kamroq. Bu qanday ma'nono bildiradi? Nima oldingi barcha raqamlarni (16 raqamidan oldin joylashgan) tekshirish shart emas: ular, albatta, biz izlayotganimizdan kichikroq bo'ladi, chunki bizning massivimiz tartiblangan! Qolgan 5 ta element orasida qidirishni davom ettiramiz. 10 Iltimos, diqqat qiling: biz faqat bitta tekshiruvni amalga oshirdik, ammo biz mumkin bo'lgan variantlarning yarmini allaqachon yo'q qildik. Bizda faqat 5 ta element qoldi. Biz qadamimizni takrorlaymiz - qolgan massivni yana 2 ga bo'ling va yana o'rta elementni oling (rasmdagi 3-qator). Bu raqam 56 va biz izlayotgan raqamdan kattaroqdir. Bu qanday ma'nono bildiradi? Biz yana 3 ta variantni - 56 raqamining o'zini va undan keyin ikkita raqamni bekor qilamiz (ular, albatta, 23 dan katta, chunki massiv tartiblangan). Tekshirish uchun bizda atigi 2 ta raqam qoldi (rasmdagi oxirgi qator) - massiv indekslari 5 va 6 bo'lgan raqamlar. Biz ulardan birinchisini tekshiramiz va bu biz qidirgan narsa - 23 raqami! Uning indeksi = 5! Keling, algoritmimiz natijalarini ko'rib chiqaylik, keyin uning murakkabligini tushunamiz. (Aytgancha, endi siz nima uchun ikkilik deb atalganini tushunasiz: uning mohiyati ma'lumotlarni doimiy ravishda 2 ga bo'lishdir). Natija juda ta'sirli! Agar biz chiziqli qidiruv yordamida kerakli raqamni qidirgan bo'lsak, bizga 10 ta tekshiruv kerak bo'ladi, lekin ikkilik qidiruv bilan biz buni 3 tada qildik! Eng yomon holatda, agar oxirgi bosqichda bizga kerak bo'lgan raqam birinchi emas, ikkinchi bo'lib chiqsa, ulardan 4 tasi bo'ladi. Uning murakkabligi haqida nima deyish mumkin? Bu juda qiziq nuqta :) Ikkilik qidiruv algoritmi chiziqli qidirish algoritmiga (ya'ni oddiy sanab o'tish) qaraganda massivdagi elementlar soniga kamroq bog'liq. At massivdagi elementlar uchun chiziqli qidiruv uchun maksimal 10 ta tekshirish kerak bo'ladi va ikkilik qidiruv uchun ko'pi bilan 4 ta tekshirish kerak bo'ladi. Farqi 2,5 baravar. Lekin bir qator uchun 1000 ta element chiziqli qidiruv uchun 1000 ta tekshiruv kerak bo'ladi va ikkilik qidirish kerak bo'ladi jami 10 ! Farqi allaqachon 100 marta! Iltimos, diqqat qiling: massivdagi elementlar soni 100 baravar oshdi (10 dan 1000 gacha), lekin ikkilik qidiruv uchun zarur tekshiruvlar soni atigi 2,5 baravarga oshdi - 4 dan 10 gacha. Agar biz 10000 element, farq yanada ta'sirchan bo'ladi: chiziqli qidiruv uchun 10 000 ta tekshiruv va faqat 14 ta tekshiruv ikkilik uchun. Va yana: elementlar soni 1000 baravar ko'paydi (10 dan 10 000 gacha), lekin tekshiruvlar soni atigi 3,5 martaga (4 dan 14 gacha) oshdi. Ikkilik qidiruv algoritmining murakkabligi logarifmikdir, yoki agar biz Big-O belgisidan foydalansak, -
Endi sizning ko'zingiz oldida rasm bor va buning uchun maksimal 14 ta tekshiruv kerakligini bilasiz. Ammo sizning ko'zingiz oldida rasm bo'lmasa va kerakli tekshiruvlarning aniq sonini hisoblashingiz kerak bo'lsa-chi? Oddiy savolga javob berish kifoya: Natija >= tekshirilayotgan elementlar soniga teng bo'lishi uchun 2 raqamini qanday darajaga ko'tarish kerak? 10000 uchun bu 14-chi kuch bo'ladi. 2 dan 13 gacha kuch juda oz (8192) Lekin 2 dan 14 gacha = 16384, bu raqam bizning shartimizni qanoatlantiradi (u >= massivdagi elementlar soni). Biz logarifmni topdik - 14. Bizga aynan shuncha chek kerak! :) Algoritmlar va ularning murakkabligi bir ma'ruzaga kiritib bo'lmaydigan darajada keng mavzu. Ammo buni bilish juda muhim: ko'plab intervyularda siz algoritmik muammolarni olasiz. Nazariya uchun men sizga bir nechta kitoblarni tavsiya qilishim mumkin. Boshlash uchun yaxshi joy bu "YouTubedagi Big-O video". Keyingi ma'ruzalarda ko'rishguncha! :)

Ko'pincha bitta muammoni hal qilish uchun bir nechta algoritmlarni o'ylab topish mumkin. Shu munosabat bilan savol tug'iladi: algoritmlarning qaysi biri "yaxshiroq"?

Ko'pgina hollarda, "yaxshiroq" algoritm bo'lib, u xuddi shu kiritilgan ma'lumotlardan foydalanib, muammoni hal qilishga, kamroq hisoblash resurslarini (xotira va vaqt) sarflaydi. Bu, albatta, jiddiy mulohaza emas. Aniqroq muhokama qilish uchun biz bir nechta tushunchalarni kiritamiz.

Algoritmning hisoblash jarayoni - bu algoritmni ba'zi kiritilgan ma'lumotlar uchun bajarishda bajariladigan qadamlar 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 bajarish uchun zarur bo'lgan vaqt \(T\).

Shubhasiz, ijro muddati individual ijrochiga bog'liq. Aytaylik, elektron kalkulyator va superkompyuter bir xil algoritmni turli vaqtlarda ishlatishi mumkin.

Biroq, vaqt \(T\) elementar harakatlar soni \(k\) va elementar harakatni bajarish uchun o'rtacha vaqt \(t\) orqali ifodalanishi mumkin:

Bundan tashqari, \(k\) xususiyatdir o'zi algoritm, \(t\) esa bajaruvchining xossasidir.

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

O'sish tartibi \(g(x)\) musbat aniq funksiya 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 bog'liqlik ham mavjud miqdorlar ma'lumotlarni kiritish \(n\) . Odatda bu \(n\) dan o'sish tartibi hisoblanadi.

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

Algoritmning vaqt murakkabligidan tashqari, u ham muhim bo'lib chiqadi fazoviy algoritmning murakkabligi.

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

\(S\) umumiy holatda ham aktuatorga bog'liq. Aytaylik, agar ikkita ijro birligi mos ravishda 4 va 8 bayt uzunlikdagi butun sonlarni qo'llab-quvvatlasa, u holda 8 baytli butun sonlardagi algoritmning fazoviy murakkabligi 4 baytli butun sonlarga qaraganda ikki baravar katta bo'ladi. Shuning uchun fazoviy murakkablik ham o'sish tartibi bilan baholanadi.

Algoritm murakkabligi sinflari

Aniq qiyinchilik sinflari: Bular o'xshash murakkablikka ega toifalar.

Quyidagi asosiy qiyinchilik sinflari ajralib turadi:

DTIME Tyuring mashinasi muammoning yechimini cheklangan vaqt ichida (qadamlar soni) topadi. Algoritmning asimptotik harakati ko'pincha belgilanadi, shuning uchun aytaylik, agar ish vaqtini oshirish tartibi \(T(n) = \mathcal(O)(f(n))\) bo'lsa, \(DTIME(f) ni ko'rsating. (n))\) . P Turing mashinasi muammoning yechimini polinom vaqtida (qadamlar soni) topadi, ya'ni. \(T(n) = \mathcal(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) = \matekal(O)(2^(n^k))\) , bu erda \(k\in \mathbb(N)\) . \(EXPTIME=DTIME(2^(n^k))\) . DSPACE Turing mashinasi cheklangan sonlar yordamida muammoning yechimini topadi qo'shimcha xotira. \(L=DSPACE(\log n)\) . PSPACE Tyuring mashinasi polinom fazoning murakkabligi bilan muammoning yechimini topadi, ya'ni \(S(n) = \mathcal(O)(n^k)\) , bu erda \(k\in \mathbb(N)\ ). \(PSPACE=DSPACE(n^k)\) . EXPSPACE Tyuring mashinasi eksponensial fazoviy murakkablikdagi muammoga yechim topadi, ya'ni

\(S(n) = \matekal(O)(2^(n^k))\) , bu erda \(k\in \mathbb(N)\) . \(EXPSPACE=DSPACE(2^(n^k))\) . Bundan tashqari, kontseptsiya bilan ishlaydigan nazariy murakkablik sinflari mavjud

deterministik bo'lmagan Tyuring mashinalari (TMT). Ularning ta'riflari yuqoridagi bilan bir xil, Tyuring mashinasi NMT bilan almashtirilgan va ularning nomlari N bilan prefikslangan (masalan, NP), NTIME va NSPACE bundan mustasno, bu erda D N bilan almashtirilgan. NMT - bu mutlaqo nazariy qurilish bo'lib, u ish printsiplari bo'yicha MTga o'xshaydi, farqi bilan har bir shtat uchun mavjud bo'lishi mumkin. ba'zilari mumkin bo'lgan harakatlar. Shu bilan birga, NMT har doim mumkin bo'lgan harakatlardan minimal mumkin bo'lgan qadamlar sonida yechimga olib keladiganini tanlaydi. Shu bilan birga, NMT hisob-kitoblarni amalga oshiradi

hamma

novdalar va minimal mumkin bo'lgan qadamlar sonida yechimga olib keladigan filialni tanlaydi. Ba'zan kvant kompyuterlari NMT ning amalga oshirilishini eshitishingiz mumkin. Ba'zi hollarda bu to'g'ri ko'rinishi mumkin bo'lsa-da, umuman olganda, NMT kvant kompyuteriga qaraganda kuchliroq tizimdir.

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

Bundan tashqari, \(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 informatikaning hal qilinmagan asosiy masalalaridan biridir.

Algoritmlarga misollar

Keling, oddiy algoritmlarga misollar keltiramiz va ularning murakkabligini ko'rib chiqamiz.

1. Butun kuchga ko'tarish
2. Ushbu algoritm Qadimgi Hindistonda bizning eramizdan oldin tasvirlangan va haqiqiy sonning \(n\) tabiiy kuchini hisoblash uchun ishlatiladi \(x\)
3. Ikkilik sanoq sistemasida \(n\) ni yozing
4. Ushbu yozuvdagi 1 ning har birini bir juft KH harfi bilan, har bir 0 ni esa K harfi bilan almashtiring.

Eng chapdagi KX juftligini kesib tashlang

Algoritmni samarali amalga oshirish uchun amalda qo'shimcha xotira talab qilinmaydi va u kiritilgan ma'lumotlarga bog'liq emas, shuning uchun fazoviy murakkablik \(S(n) = \mathcal(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 samaralidir.

Butun sonlarni ko'paytirish

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

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

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

Butun sonlarni bo'lish va 2 ga ko'paytirishni siljish orqali amalga oshirish mumkin bo'lganligi sababli, bu algoritm \(2 \log_2 n\) siljish amallarini ishlab chiqaradi, bu erda \(n\) ikkita sondan kichikroqdir. Eng yomon holatda, xuddi shu natija \(\log_2 n - 1\) qo'shish amallarini beradi. Qanday bo'lmasin, vaqtning murakkabligi \(T(n) = \mathcal(O)(\log n)\).

Algoritmni samarali amalga oshirish uchun amalda qo'shimcha xotira 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'paytirish.

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 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, algoritm murakkabligining bir nechta taxminlari mavjud.

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

Vaqtinchalik murakkablik - uzunlikdagi kirish ma'lumotlari bo'yicha algoritmning ishlash vaqtining asimptotik bahosi p. Ko'rinib turibdiki, 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 formulalari 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 skalyar miqdorlar sonining asimptotik bahosi p.

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

Kognitiv murakkablik - bu algoritmni qo'llash sohalaridagi mutaxassislar tushunishi uchun mavjud bo'lgan xususiyatdir.

Asimptotikaning turlari va belgilari

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 funksiyasini /(«) yoki algoritmning operatsion murakkabligini asimptotik aniq baholash;
• 2) /(n) = 0(§(n)) - murakkablik funksiyasi uchun asimptotik aniq yuqori chegara /( n);
• 3) /(l) = ?2(#(l)) - murakkablik funksiyasi uchun asimptotik aniq pastki chegara /( p).

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

Keling, formulalar semantikasini misol yordamida tushuntirib beraylik: agar /(i) = 0(^2(l)) yozilsa, BU funktsiyani bildiradi. g(n)=og2 (n) murakkablik funksiyasining asimptotik aniq bahosi /(«). Aslida, bayonot shaklida ikki pozitsiyali ta'rif mavjud:

Agar f(n)= @(log 2()),

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

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

Asimptotiklarning rasmiy ta'riflari

Murakkablik funksiyasining asimptotik aniq bahosi Bilan, Bilan 2, l 0, shundayki, l>l 0 uchun /(l), doimiy omillargacha, funksiyadan farq qilmaydi. g( l), keyin funksiya g(n) f(n) funksiyaning asimptotik aniq bahosi deyiladi.

• 3 s ], s 2 e VA, c x > 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: musbat raqamlar mavjud bo'lsa Bilan va l 0 shunday bo'lsinki, l>l 0 uchun /(l) funksiya funksiyadan tez o'smaydi. g(n) doimiy c koeffitsientigacha, keyin funksiya g(n) funksiya uchun asimptotik aniq yuqori chegara deyiladi Ap).

Ta'rifning aniqroq rasmiy ifodasi:

• 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 funksiyasi uchun asimptotik qattiq pastki chegara og'zaki ravishda quyidagicha aniqlanadi: musbat raqamlar mavjud bo'lsa Bilan va l 0 shunday bo'lsinki, l>l 0 uchun /(l) funksiya funksiyadan sekin o'smaydi. g(n) doimiy omilgacha Bilan, u holda funksiya?(l) funksiya uchun asimptotik aniq pastki chegara deyiladi

Ta'rifning aniqroq rasmiy ifodasi:

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

/(I) = 0.^(n))

Quyidagilarga e'tibor bering:

• 1) asimptotikaning rasmiy ta'riflarida ko'rsatilgan tengsizliklar, umumiy holda, bitta emas, balki ma'lum funktsiyalar to'plami bilan, ko'pincha son-sanoqsiz a'zolar bilan, shuning uchun konstruktsiyalar bilan qanoatlantirilishi mumkin. Q(g(n)), 0^(n)) Va 0.^(n)) ramziy qiladi ko'p funktsiyalar, u bilan o'rganilgan mehnat intensivligi funktsiyasi /(i) solishtiriladi; shu sababli, asimptotikaning belgilarida /(i) = 0(?(i)), /(/0 = O(? max (l)), Dia) = ?2(? t1n (i) ) “=” belgisi o‘rniga “e” belgisidan foydalanish oqilonaroq bo‘lardi;
• 2) dizaynlar (d ^ (n)), 0^(n)) Va ?1^(n)), Muayyan miqdorlar uchun belgi sifatida foydalanilganda, mos ravishda quyidagicha o'qilishi kerak: mos keladigan har qanday funktsiya tezroq o'smaydi va sekin o'smaydi g(n).

Asimptotiklarning tasodif va farqi

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

Asimptotikaning quyidagi xossasi juda aniq: agar taxmin f(n) = ©^(n)) mavjud bo'lsa, tengliklar /( n) = 0(^(i)) va /(i) = ?2(#(i)), ya'ni. mehnat intensivligining yuqori va pastki baholari bir-biriga to'g'ri keladi; agar /(i) = 0(? max(i)) va f(n) = C1^ mt(n)), Va g max (n)fg m 1p (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 manba ma'lumotlarining o'ziga xos qiymatlariga bog'liq emas; masalan, chiziqli tizimlarni yechish algoritmidagi ko'paytirish va bo'lish amallari sonining noma'lum miqdorlar soniga bog'liqlik funktsiyalari. algebraik tenglamalar IZ parchalanish usuli;
• 2) murakkablik funksiyasi tasodifiy funktsiyadir, ya'ni. bajarilgan operatsiyalar soni manba ma'lumotlarining o'ziga xos xususiyatlariga va (yoki) ularni olish tartibiga bog'liq bo'lib, siz / m|n (i), / max (i) funktsiyalarini belgilashingiz mumkin, minimal va maksimal sonini tavsiflaydi. algoritm ijrochisi tomonidan ma'lum bir kirish uzunligi i uchun bajariladigan amallar, ammo, bu funktsiyalarning ikkalasi ham bir xil dominantlarga ega - masalan, ular bir xil tartibdagi ko'phadlardir.

Operatsion murakkablik buyurtmalarini 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 murakkabliklari 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). +p 2 +p) = 0 (i 5).

Yuqoridagi qoidalar faqat bitta asimptotik bahoning 0(") belgisidan foydalanadi, 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, a,b - soni konstantalar bo‘lsa, quyidagi gaplar to‘g‘ri bo‘ladi: I" dominates I!; I! dominates a"; a" Zj ustunlik qiladi" agar a>b a p hukmronlik qiladi n b, agar A har qanday uchun > 1 b e 9? ; p a a/ hukmronlik qiladi, agar a>b i log d(i) agarda hukmronlik qiladi A > 1.

O'rtacha mehnat intensivligini baholash

Amalda, qayta Matematik hisob-kitoblarda, M ning murakkabligini matematik kutishning f (i) ni baholash katta qiziqish uyg'otadi, chunki aksariyat hollarda f (i) tasodifiy funktsiyadir. Biroq, tasodifiy /(i) bilan algoritmlarni eksperimental o'rganish jarayonida paydo bo'ladi qo'shimcha muammo- M.ni ishonchli baholash uchun testlar sonini tanlash. Bu muammoni yengish asosiy vazifa hisoblanadi. Taklif etilayotgan yechim /(i) ga yaqinlashishi uchun beta taqsimotidan foydalanishga asoslangan. Bu juda konstruktiv va universal texnika. Biroq, zamonaviy sharoitda, kompyuterning ishlashi ancha yuqori bo'lsa, ko'p hollarda qiymatlarning joriy o'zgaruvchanligini kuzatish asosida testlar hajmini tanlashning oddiy usulidan foydalanish mumkin. f(n) - qiymatlar baholarning o'zgaruvchanligi belgilangan xatodan kam bo'lmaguncha 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 qo'ng'iroqlarni tahlil qilish bilan bog'liq.

O'chirish algoritmini ko'rib chiqing Kimga o'lchamdagi massivdan th element n dan harakatlanuvchi massiv elementlaridan iborat (k + 1) oldingi n-massivning boshiga qaytish va elementlar sonini kamaytirish n birlik uchun. Massivni qayta ishlash siklining murakkabligi O(p-k), chunki tsiklning tanasi (harakatlanish operatsiyasi) bajariladi Kompyuter marta, va pastadir tanasining murakkabligi 0 (1), ya'ni. doimiy hisoblanadi.

Ko'rib chiqilayotgan misolda murakkablik 0(") asimptotikasi 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 mos keladi: f(n) = Q(n-k), f(n) = 0(n-k) Va f(n) = Q(n-k). Bu fakt ©( ) belgisi bilan tasdiqlanadi. 0(*) va/yoki?2(*) dan faqat ushbu asimptotiklar farq qilsagina foydalanishingiz kerak.

Loop turi (for, while, takrorlash) murakkablikka ta'sir qilmaydi. Agar bitta pastadir boshqasiga o'rnatilgan bo'lsa va ikkala tsikl ham bir xil o'zgaruvchining o'lchamiga bog'liq bo'lsa, u holda butun struktura kvadratik murakkablik bilan tavsiflanadi. Takrorlashlarni joylashtirish murakkablikni oshirishning asosiy omilidir. Misol sifatida biz o'lchamdagi massiv uchun taniqli qidiruv va saralash algoritmlarining murakkabligini keltiramiz. p:

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

E'tibor bering, oddiy almashinuv usulida taqqoslash operatsiyalari soni asimptotik xatti-harakatlarga ega 0(n 2) va almashtirish operatsiyalari soni ikki xil asimptotikaga ega 0(n 2) va?2(0), chunki taqqoslashlar soni saralanayotgan ma'lumotlar qiymatlarining o'ziga xos xususiyatlariga bog'liq emas, almashtirishlar soni esa aynan shu xususiyatlar bilan 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 n 2 - tartiblangan massiv dastlab teskari yo'nalishda tartiblangan bo'lsa.

Funktsiya nomi g(n) asimptotikada /(l) = @(^(l)) va /(«) = 0(g(n)) algoritmni xarakterlash uchun murakkablik funksiyasi /(«) ishlatiladi. Shunday qilib, ular polinom, eksponensial, logarifmik va hokazo murakkablik algoritmlari haqida gapiradilar.

Qiyinchilik funktsiyasi 0(1). Doimiy murakkablik algoritmlarida dasturdagi amallarning aksariyati bir yoki bir necha marta bajariladi. Har doim bir xil vaqtni talab qiladigan (ma'lumotlar hajmidan qat'iy nazar) har qanday algoritm doimiy murakkablikka ega.

Murakkablik funksiyasi 0(N). Dasturning ishlash vaqti odatda chiziqli bo'lib, unda kiritilgan ma'lumotlarning har bir elementi faqat chiziqli marta qayta ishlanishi kerak. Bu murakkablik funksiyasi oddiy siklni xarakterlaydi.

Murakkablik funksiyasi 0(N 2), 0(N 3), 0(№) - polinom murakkablik funktsiyasi: operatsiyalar soni kvadrat bilan ortadi N. Umumiy holatda, masalaning murakkabligiga qarab, O(A^) bo'lishi mumkin. Bu murakkablik funksiyasi murakkab siklni xarakterlaydi.

Qiyinchilik funktsiyasi O(Jurnal 2 (A0), 0(N log2 (A0). Bu algoritmlar katta muammoni ko'plab kichiklarga ajratadigan va keyin ularni hal qilib, echimlarni birlashtiradigan vaqt.

Murakkablik funksiyasi 0(e N). Eksponensial murakkablikdagi algoritmlar ko'pincha qo'pol kuch deb ataladigan yondashuvdan kelib chiqadi.

Murakkablik funksiyasi 0(M) - operatsiyalar soni faktorialga mutanosib ravishda oshadi N.

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 qo'ng'iroqlarni tahlil qilish bilan bog'liq.

Masalan, massiv elementlarini qayta ishlash algoritmini ko'rib chiqing.

/" uchun: = 1 gacha N boshlang

Ushbu algoritmning murakkabligi HAQIDA(A), chunki sikl tanasi A marta bajariladi va tsikl tanasining murakkabligi 0(1) ga teng. Agar bitta pastadir boshqasiga o'rnatilgan bo'lsa va ikkala tsikl ham bir xil o'zgaruvchining o'lchamiga bog'liq bo'lsa, u holda butun struktura kvadratik murakkablik bilan tavsiflanadi.

/ uchun: = 1 gacha N uchun qiling j: = 1 gacha N boshlang

Ushbu dasturning murakkabligi 0 (N 2).

1-misol. Klaviaturadan massivga kiruvchi va undagi eng katta elementni topadigan dasturning murakkabligini baholaylik. Algoritm quyidagi bosqichlardan iborat:

• - massivni kiritish (siz A elementlarini o'qishingiz kerak);
• - eng katta elementni qidirish (siz A - 1 taqqoslashingiz kerak);
• - natijani chiqarish (siz bitta raqam yoki qatorni chiqarishingiz kerak).

A + (A - 1) + 1 = 2A operatsiyalar sonini qo'shamiz, ya'ni. mavjud

shunday doimiyki, har qanday A uchun operatsiyalar soni CA dan oshmaydi. Shuning uchun algoritmning murakkabligi 0(A) ga teng.

2-misol. Klaviaturadan massivga kiruvchi va undan berilgan xossaga ega (masalan, ma’lum qiymatga teng) elementni topadigan dasturning murakkabligini baholaylik. Algoritm quyidagi bosqichlardan iborat:

• - massivni kiritish (Kirish operatsiyalari);
• - berilgan xususiyatga ega elementni qidirish (element massivning boshiga yaqinroq yoki eng oxirida joylashgan bo'lishi mumkin; agar element mavjud bo'lmasa, bunga ishonch hosil qilish uchun barcha A taqqoslashlarini amalga oshirish kerak);
• - natijaning chiqishi.

Eng yaxshi holatda, ko'rsatilgan algoritm A + 2 operatsiyalarini (butun massivni kiritish, bitta taqqoslash, chiqish), eng yomon holatda (bunday element bo'lmaganda, 2A + 1 operatsiyani) talab qiladi. Agar A bo'lsa katta raqam, masalan, 10 6 tartibidan, keyin birlikni e'tiborsiz qoldirish mumkin. Shuning uchun algoritmning murakkabligi ga teng 0(N).

3-misol. Uzunlikdagi so'z uchun shifrlash algoritmining murakkablik funksiyasini aniqlaylik L almashtirish usuli bilan. Jadval bo'lsin, unda alifboning har bir belgisi uchun uni almashtirish kerak bo'lgan belgi yoziladi. Keling, alifbodagi harflar sonini belgilaylik S. Algoritm quyidagi bosqichlardan iborat:

• - so'zni kiritish (bitta operatsiya);
• - tsiklni tashkil etish:
  • 1) har bir belgi uchun jadvalda uning o'rnini toping (agar jadval buyurtma qilinmagan bo'lsa va qidiruvni osonlashtiradigan xususiyatlarga ega bo'lmasa, eng yomon holatda sizga kerak bo'ladi. S agar qidirilayotgan element eng oxirida bo'lsa, bitta belgi uchun operatsiyalar);
  • 2) topilgan belgining chiqishi;
• - tsiklning oxiri.

Operatsiyalarning umumiy soni 1+ (S+) L. Etarli darajada katta bo'lsa S Va L birliklarni e'tiborsiz qoldirish mumkin va ma'lum bo'lishicha, berilgan algoritmning murakkablik funktsiyasi O(S L).

4-misol. Natural sonlarni tarjima qilish algoritmining murakkablik funksiyasini aniqlaylik 1 V ikkilik sanoq sistemasiga (ma'lumotlarni kiritish va chiqarish operatsiyalarisiz). Algoritm quyidagi bosqichlardan iborat:

• - raqamni 2 ga bo'lish natijasi 0 ga teng bo'lguncha tsikl:
• - raqamni 2 ga bo'ling va qolganini eslang;
• - bo'lish natijasini yangi raqam sifatida qabul qilish;
• - tsiklning oxiri.

Amaliyotlarning umumiy soni 1 + log 2 A dan oshmaydi. Shuning uchun tasvirlangan algoritm murakkablikka ega. 0 (og 2 N).

Belgilash	Intuitiv tushuntirish	Ta'rif
	f yuqorida funksiya bilan chegaralangan g	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> yoki style="maks-kenglik: 98%; balandlik: avtomatik; kenglik: avtomatik;" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
	f quyida funksiya bilan chegaralangan g(doimiy omilgacha) asimptotik	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
	f pastdan va yuqoridan funksiya bilan chegaralangan g asimptotik tarzda	0), n_0: \forall (n>n_0) \; |Cg(n)|
	g hukmronlik qiladi f asimptotik tarzda	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
	f hukmronlik qiladi g asimptotik tarzda	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
	f ekvivalent g asimptotik tarzda

Misollar

Eslatmalar

Shuni ta'kidlash kerakki, eng yomon bajarilish vaqtining o'sish darajasi algoritmlar va dasturlarni baholashning yagona yoki eng muhim mezoni emas. Ish vaqti mezoniga boshqa nuqtai nazardan qarashga imkon beruvchi bir nechta fikrlar:

Agar n-cho'qqi grafigi uchun ma'lum bir masalani bitta algoritm bilan hal qilish uchun n C tartibli vaqt (qadamlar soni) va boshqasi bilan - n+n!/C tartib kerak bo'lsa, bu erda C doimiy son, keyin "ko'p nomli mafkura" ga ko'ra, birinchi algoritm amalda samarali , lekin ikkinchisi emas, garchi, masalan, C = 10 (10 10) da vaziyat aksincha.

1. Samarali, lekin murakkab algoritmlar, agar istalmagan bo'lishi mumkin tayyor dasturlar ushbu dasturlarni yozishda ishtirok etmagan shaxslar tomonidan qo'llab-quvvatlanadi. Umid qilamizki, samarali algoritmlarni yaratish texnologiyasining asosiy jihatlari keng ma'lum va juda murakkab algoritmlar amaliyotda erkin qo'llaniladi. Shu bilan birga, samarali, ammo "hiyla-nayrang" algoritmlar ularning murakkabligi va ularni tushunishga urinishda yuzaga keladigan qiyinchiliklar tufayli talabga ega bo'lmasligi mumkinligini hisobga olish kerak.
2. Samarali algoritmlar bunday katta hajmdagi kompyuter xotirasini talab qiladigan bir nechta misollar mavjud (sekinroqlarini ishlatish imkoniyatisiz). tashqi mablag'lar saqlash) bu omil algoritmning "samaradorlik" ustunligini inkor etadi.
3. Raqamli algoritmlarda algoritmlarning aniqligi va barqarorligi ularning vaqt samaradorligidan kam emas.

Qiyinchilik sinflari

Murakkablik sinfi - hisoblash murakkabligi bo'yicha o'xshash algoritmlar mavjud bo'lgan tanib olish muammolari to'plami. Ikki muhim vakil:

P sinf

P va NP sinflarining tengligi muammosi

Mashhur olimlar

• Leonid Levin
• Aleksandr Razborov
• Eddi Shamir

Shuningdek qarang

Havolalar

• Yuriy Lifshits “Nazariy informatikaning zamonaviy muammolari”. NP-qiyin masalalar algoritmlari bo'yicha ma'ruzalar kursi.
• A. A. Razborov Nazariy informatika: matematikning nuqtai nazari // Kompyuter. - 2001. - No 2. (muqobil havola)
• A. A. Razborov Hisob-kitoblarning murakkabligi to'g'risida // Matematik ta'lim. - MCNMO, 1999. - No 3. - B. 127-141.

Wikimedia fondi.

2010 yil.

Boshqa lug'atlarda "Algoritmning vaqt murakkabligi" nima ekanligini ko'ring: vaqt murakkabligi (algoritmning) - — Mavzular ma'lumotlarini himoya qilish EN vaqt murakkabligi...

Texnik tarjimon uchun qo'llanma- boshqaruv tizimida shaxsning zarur funktsiyalarini bajarish sifati va davomiyligiga ta'sir qiluvchi ob'ektiv omillar to'plami. S. o. va boshqalar bir necha turlarga bo'linadi, ularning har biri ma'lum bir tarzda omillarning kombinatsiyasi bilan tavsiflanadi... ... Psixologiya va pedagogikaning entsiklopedik lug'ati

Algoritmni manba ma'lumotlariga qo'llash jarayonlarining qiyinligi (og'irligi) ning raqamli bahosini beradigan hisoblash funktsiyasi. A. s.ga aniqlik kiritib. Hisob-kitoblarga signalizatsiya funktsiyasi (yoki oddiygina signalizatsiya) funktsiyasi tushunchasi xizmat qiladi, u berilgan... ... Matematik entsiklopediya

Informatika va algoritm nazariyasida algoritmning hisoblash murakkabligi - bu qandaydir algoritm tomonidan bajariladigan ish hajmining kiritilgan ma'lumotlar hajmiga bog'liqligini aniqlaydigan funktsiyadir. Hisoblash murakkabligini o'rganadigan bo'lim nazariya ... ... Vikipediya deb ataladi

Informatikada hisoblash murakkabligi nazariyasi hisoblash nazariyasining bir tarmog'i bo'lib, hisoblash muammosini hal qilish uchun zarur bo'lgan ishlarning narxini o'rganadi. Qiymat odatda... ... Vikipediya deb ataladigan mavhum vaqt va makon tushunchalari bilan o'lchanadi

Bu ro'yxatdagi elementlarni tartiblash algoritmidir. Ro'yxat elementi bir nechta maydonlarga ega bo'lsa, tartiblash mezoni bo'lib xizmat qiladigan maydon saralash kaliti deb ataladi. Amalda, raqam ko'pincha kalit sifatida ishlatiladi va boshqa sohalarda ... ... Vikipediya

Saralash algoritmi - bu ro'yxatdagi elementlarni tartiblash algoritmi. Ro'yxat elementi bir nechta maydonlarga ega bo'lsa, tartiblash mezoni bo'lib xizmat qiladigan maydon saralash kaliti deb ataladi. Amalda, raqam ko'pincha kalit sifatida ishlatiladi va ... ... Vikipediya

- (GM) kriptografik tizim bilan umumiy kalit, 1982 yilda Shafi Goldwasser va Silvio Micali tomonidan ishlab chiqilgan. GM - bu standart kriptografiya ostida kuchli ekanligi isbotlangan birinchi ehtimolli ochiq kalit shifrlash sxemasi... ... Vikipediya Batafsil o'qing

Ulanish