Algoritmning murakkabligi

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 algoritmlar haqida gaplashamiz . Algoritm nima? Oddiy qilib aytganda, bu kerakli natijaga erishish uchun bajarilishi kerak bo'lgan ma'lum 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 beradi?

1. Budilnikda uyg'onish.
2. Dush qabul qiling, yuzingizni yuving.
3. Nonushta tayyorlang, qahva / choy tayyorlang.
4. Yemoq.
5. Kechqurun kiyimingizni dazmollamagan bo'lsangiz, dazmollang.
6. Kiyinib oling.
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 vazifaga duch kelasiz: massivdagi 100 ta nomdan iborat ro'yxatni tartiblash . Bu muammo juda oddiy, ammo uni turli yo'llar bilan hal qilish mumkin. 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. Ushbu yechim samarali bo'ladimi ? Qiyin. Bu erda biz algoritmlarning yana bir juda muhim xususiyatiga keldik - ularning samaradorligi . 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. Ammo bu samarasiz yechim bo'ladi - bu juda ko'p vaqt va 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 Big-O (“katta O”) deb nomlangan maxsus belgi yaratildi . 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, siz 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. Bu bir necha daqiqa vaqt oladi! 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, 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 ketadimi? Ha, bo'ladi! Endi biz algoritmimizning muhim xususiyatini bilamiz: uzatiladigan ma'lumotlarning o'lchami 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 chiziqli bo'ladi. "Chiziqli" ma'lumotlar hajmi oshgani sayin, uni uzatish vaqti taxminan proportsional 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 belgisidan foydalanib, bizning algoritmimizning murakkabligi O(N) sifatida aniqlanadi . Bu belgi kelajakda foydalanish uchun yaxshi eslab qolinadi; 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 bu mantiqqa to'g'ri kelmaydi - baribir biz uni nazorat qila olmaymiz. Big-O algoritmning o'zini, u ishlashi kerak bo'lgan "muhitdan" qat'i nazar, baholaydi. 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 Demak, 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: deylik, 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 murakkablikka ega . "Doimiy" algoritmga uzatilgan ma'lumotlarga bog'liq emasligini anglatadi. Yuk mashinasiga 1 Gb hajmli flesh-disk qo'ying va 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 O (1) sifatida belgilanadi . Biz O(N) bilan tanishganimizdan beri vaO(1) , endi ko'proq "dasturchi" misollarini ko'rib chiqamiz :) Aytaylik, sizga 100 ta raqamdan iborat massiv berilgan va vazifa ularning har birini konsolga chop etishdir. forSiz ushbu vazifani bajaradigan muntazam tsiklni yozasiz

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

Yozilgan algoritmning murakkabligi nimada? Chiziqli, O(N). Dastur bajarishi kerak bo'lgan harakatlar soni unga qancha raqam kiritilganiga bog'liq. 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, biz N massivdan o'tishimiz va konsolga N chiqishni bajarishimiz kerak . Keling, yana bir misolni ko'rib chiqaylik.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

Bizda bo'sh raqam bor LinkedList, unga biz bir nechta raqamlarni kiritamiz. Bizning misolimizga bitta raqamni kiritish algoritmining murakkabligini LinkedListva bu ro'yxatdagi elementlar soniga qanday bog'liqligini taxmin qilishimiz kerak. Javob: O(1) - doimiy murakkablik . Nega? E'tibor bering: har safar ro'yxatning boshiga raqam kiritamiz. Bundan tashqari, siz eslayotganingizdek, raqamlarni elementlarga kiritishda ular hech qanday joyga siljimaydi - havolalar qayta aniqlanadi (agar siz to'satdan LinkedList qanday ishlashini unutgan bo'lsangiz, bizning eski ma'ruzalarimizniLinkedList ko'rib chiqing ). Agar hozir ro'yxatimizda birinchi raqam raqam bo'lsa va biz ro'yxatning boshiga y raqamini qo'shsak, faqat kerak bo'ladi: х

x.previous  = y;
y.previous = null;
y.next = x;

Ushbu ma'lumotni qayta ta'riflash uchun biz uchun hozir qancha raqam borligi muhim emasLinkedList - kamida bitta, kamida milliard. Algoritmning murakkabligi doimiy bo'ladi - O(1).

Logarifmik murakkablik

Vahimaga tushma! :) Agar "logarifmik" so'zi sizni ma'ruzani yopish va boshqa o'qishni xohlamasa, bir necha daqiqa kuting. Bu erda hech qanday matematik qiyinchiliklar bo'lmaydi (boshqa joylarda bunday tushuntirishlar juda ko'p) va biz barcha misollarni "barmoqlarda" tahlil qilamiz. Tasavvur qiling-a, sizning vazifangiz 100 ta raqamdan iborat massivda bitta aniq raqamni topishdir. Aniqrog'i, u umuman bor yoki yo'qligini tekshiring. Kerakli raqam topilgandan so'ng, 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, unda keyingi elementga 100 marta o'tishimiz va raqamni 100 marta o'yin uchun 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. Buning o'rniga biz taniqli ikkilik qidiruv algoritmidan foydalanishimiz mumkin . 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 nimani anglatadi? Oldingi barcha raqamlarni (16-raqamgacha joylashgan) tekshirish shart emas : ular biz izlayotgan raqamdan albatta kamroq bo'ladi, chunki bizning massivimiz tartiblangan! Qolgan 5 ta element orasida qidirishni davom ettiramiz. Diqqat qilish:Biz faqat bitta tekshiruvni amalga oshirdik, lekin biz allaqachon mumkin bo'lgan variantlarning yarmini 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 nimani anglatadi? 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 qidirayotgan 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. Massivdagi 10 ta element bilan chiziqli qidiruv uchun maksimal 10 ta tekshiruv, ikkilik qidiruv esa koʻpi bilan 4 ta tekshirish kerak boʻladi. Farqi 2,5 baravar. Ammo 1000 ta elementdan iborat massiv uchun chiziqli qidiruv uchun 1000 ta tekshirish kerak bo'ladi va ikkilik qidiruvga atigi 10 ta kerak bo'ladi ! Farqi allaqachon 100 marta! Diqqat qilish:massivdagi elementlar soni 100 baravarga (10 dan 1000 gacha) oshdi va ikkilik qidiruv uchun zarur tekshiruvlar soni atigi 2,5 baravarga oshdi - 4 dan 10 gacha. Agar biz 10 000 ta elementga erishsak , farq yanada ta'sirchan: 10 000 ta. chiziqli qidiruvni tekshiradi va ikkilik uchun jami 14 ta tekshiruv . 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 logarifmik yoki Big-O belgisida O(log n) dir . Nega bunday deb ataladi? Logarifm - bu darajaga teskari ko'rsatkich. Ikkilik logarifm 2 ning kuchini hisoblash uchun ishlatiladi. Masalan, bizda ikkilik qidiruv yordamida o'tishimiz kerak bo'lgan 10 000 element mavjud. 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: olingan natija >= tekshirilayotgan elementlar soni bo'lishi uchun 2 raqamini qanday kuchga ko'tarish kerak? 10000 uchun bu 14-chi kuch bo'ladi. 2 dan 13 darajagacha juda kichik (8192) Lekin 2 dan 14 darajagacha = 16384 , bu raqam bizning shartimizni qondiradi (bu >= massivdagi elementlar soni). Biz logarifmni topdik - 14. Bizga qancha 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 - " Grocking Algoritms ": kitobdagi misollar Python tilida yozilgan bo'lsa-da, kitob tili va misollari juda oddiy. Yangi boshlanuvchilar uchun eng yaxshi variant va u ham kichik hajmga ega. Yana jiddiy o'qish: Robert Laforet va Robert Sedgwick kitoblari . Ikkalasi ham Java tilida yozilgan, bu sizga o'rganishni biroz osonlashtiradi. Axir, siz bu til bilan yaxshi tanishsiz! :) Yaxshi matematik bilimga ega talabalar uchun eng yaxshi variant Tomas Kormanning kitobi bo'ladi . Ammo siz faqat nazariya bilan qoniqmaysiz! “Biling” != “mumkin” Siz HackerRank va Leetcode da algoritm masalalarini yechishda mashq qilishingiz mumkin . U yerdagi muammolar ko'pincha Google va Facebook-da intervyu paytida ham qo'llaniladi, shuning uchun siz zerikmaysiz :) Ma'ruza materialini mustahkamlash uchun YouTube'da Big-O haqida ajoyib video tomosha qilishni maslahat beraman. Keyingi ma'ruzalarda ko'rishguncha! :)