Algoritmlar

5.1 Algoritm nima?

Algoritm deganda biror muammoni yechishning aniq, qadamli ko'rsatmasi tushuniladi. Bu kompyuterga xos tushuncha emas: oshxonadagi retsept ham, yo'l ko'rsatmasi ham algoritm. Aniq qadamlar, aniq tartib, aniq natija.

Dasturlashda esa bir vazifani ko'pincha bir necha xil algoritm bilan bajarsa bo'ladi. Masalan, telefon kitobchasidan biror ismni topish. Birinchi sahifadan oxirigacha varaqlab borish ham bo'ladi, kitobchani o'rtasidan ochib, qaysi yarmida ekanini aniqlab borish ham. Ikkalasi to'g'ri natija beradi, lekin biri ancha tezroq.

Aynan shu yerda samaradorlik (efficiency) muhim bo'ladi: algoritm qancha qadamda ishni tugatadi. Kichik ma'lumotda farq sezilmaydi, lekin million elementli ro'yxatda sekin algoritm soatlab, tez algoritm soniyalarda ishlashi mumkin.

5.2 Chiziqli qidiruv

Chiziqli qidiruv (linear search) eng oddiy usul: massivni boshidan boshlab, har bir elementni navbatma-navbat tekshiramiz, qidirilgan qiymatni topguncha yoki oxiriga yetguncha. O'tgan haftadagi sikl bilan massiv bo'ylab yurish, aynan shu.

Pastda qidiriladigan sonni o'zgartiring va Keyingi qadam bilan har bir tekshiruvni kuzating. Sariq katak hozir tekshirilayotgan element, yashil katak esa topilgan joy:

Eng yomon holatda (qiymat oxirida yoki umuman yo'q bo'lsa) biz barcha elementni tekshiramiz. Demak 100 elementga 100 qadam, million elementga million qadam kerak bo'lishi mumkin. Bu sekin, lekin u saralanmagan massivda ham ishlaydi, mana shunisi qulay.

5.3 Ikkilik qidiruv

Agar massiv saralangan bo'lsa (kichikdan kattaga tartiblangan), ancha aqlli usul bor: ikkilik qidiruv (binary search). G'oya telefon kitobchasinikiga o'xshaydi: o'rtasini ochamiz. Agar qidirilgan qiymat o'rtadagidan katta bo'lsa, chap yarmiga umuman qaramaymiz; kichik bo'lsa, o'ng yarmiga qaramaymiz. Har qadamda qolgan oraliq ikki barobar qisqaradi.

Pastda saralangan massiv. Qiymat tanlang va kuzating: och katak hali ko'rib chiqilayotgan oraliq, sariq katak o'rta, yashil katak topilgan joy:

Mana sehr: 8 elementli massivni ikkilik qidiruv eng ko'pi bilan 3 qadamda ko'rib chiqadi, chunki har safar yarmini tashlab yuboramiz (8 → 4 → 2 → 1). Million element uchun esa atigi 20 qadam yetadi! Lekin bitta shart bor: massiv oldindan saralangan bo'lishi kerak.

Bashorat qiling

5.4 Samaradorlik: Big-O

Algoritmlar tezligini taqqoslash uchun dasturchilar Big-O belgisidan foydalanadi. U aniq vaqtni emas, balki ma'lumot hajmi (n) oshganda qadamlar soni qanday o'sishini ko'rsatadi. Eng ko'p uchraydiganlari:

• O(1) doimiy: hajm qancha bo'lsa ham, bir xil qadam. Eng tez
• O(log n) logarifmik: hajm ikki barobar oshsa, atigi bitta qadam qo'shiladi. Ikkilik qidiruv shunday
• O(n) chiziqli: hajmga teng. Chiziqli qidiruv shunday
• O(n^2) kvadratik: hajm kvadrati. Oddiy saralashlar shunday, sekin

Pastda n ni tanlang va har bir tezlik turi nechta qadam talab qilishini solishtiring:

5.5 Saralash nima va nega kerak?

Saralash (sorting) deganda massiv elementlarini biror tartibga, masalan kichikdan kattaga, joylash tushuniladi. Telefon kontaktlari alifbo bo'yicha, do'kon mahsulotlari narx bo'yicha, imtihon natijalari ball bo'yicha: bularning hammasi saralash.

Saralash yana bitta sababdan muhim: u boshqa algoritmlarni tezlashtiradi. Eslang, ikkilik qidiruv faqat saralangan massivda ishlardi. Demak bir marta saralab qo'ysak, keyin minglab marta tez qidirishimiz mumkin.

Saralashning ko'plab usuli bor. Biz ikkita sodda, lekin o'rganish uchun ajoyib usulni ko'ramiz: pufaksimon va tanlab saralash. Ikkalasini ustun-diagramma ko'rinishida jonli kuzatamiz, bunda balandlik qiymatni bildiradi.

5.6 Pufaksimon saralash

Pufaksimon saralash (bubble sort) eng oson tushuniladigan usul. G'oya: qo'shni ikki elementni solishtiramiz, agar chapdagisi kattaroq bo'lsa, joylarini almashtiramiz. Massiv bo'ylab shunday yurib chiqamiz, keyin yana boshidan, toki birorta almashtirish kerak bo'lmay qolguncha. Har bir o'tishda eng katta element xuddi pufakdek oxirgi joyiga "ko'tarilib" boradi.

Keyingi qadam bilan har bir solishtirish va almashtirishni kuzating. Sariq ustunlar hozir solishtirilayotganlar, to'q sariq esa almashtirilayotganlar, yashil ustunlar o'z joyini topganlar:

Pufaksimon saralash sodda, lekin sekin: u har bir juftni qayta-qayta solishtirgani uchun samaradorligi O(n^2). Ya'ni 100 element uchun taxminan 10 000 amal. Kichik massivlar uchun yaxshi, katta uchun yaramaydi.

5.7 Tanlab saralash

Tanlab saralash (selection sort) boshqacha strategiya: har safar qolgan saralanmagan qismdan eng kichik elementni topib, uni oldinga qo'yamiz. Birinchi o'tishda butun massivdan eng kichigini topib 0-o'ringa, ikkinchisida qolganidan eng kichigini 1-o'ringa, va hokazo.

Pastda kuzating: sariq ustun hozir tekshirilayotgan element, to'q sariq esa shu paytgacha topilgan eng kichik nomzod, yashil ustunlar o'z joyini topganlar:

Tanlab saralash ham O(n^2): u ham har element uchun qolganlarini ko'rib chiqadi. Lekin u kamroq almashtirish qiladi (har o'tishda atigi bitta), shuning uchun ba'zi holatlarda pufaksimondan amaliyroq.

5.8 Algoritmlarni solishtirish

Endi ko'rganlarimizni bitta jadvalda solishtiramiz. Diqqat qiling: tezlik nafaqat algoritmga, balki shartga ham bog'liq (masalan, ikkilik qidiruv saralangan massiv talab qiladi).

Saralashning tezroq usullari ham bor (masalan, birlashtirib saralash, O(n log n)), ularni quyida va keyingi haftalarda ko'ramiz. Hozircha asosiy xulosa: O(log n) juda tez, O(n) o'rtacha, O(n^2) esa katta hajmda sekin.

5.9 Amaliy: qaysi algoritmni tanlash?

Eng yaxshi algoritm degan narsa yo'q, vaziyatga qarab tanlanadi. Mana sodda qoidalar:

• Massiv kichik yoki bir martagina qidirsangiz: chiziqli qidiruv yetarli, soddaroq
• Bir massivda ko'p marta qidirsangiz: avval bir marta saralang, keyin ikkilik qidiruv ishlating
• Ma'lumot saralanmagan va katta bo'lsa: oddiy saralashlar emas, tezroq usul (O(n log n)) tanlang
• O'rganish yoki kichik vazifa uchun: pufaksimon va tanlab saralash mukammal, kodi qisqa

5.10 Chuqurroq advanced

Asosiy algoritmlarni ko'rdingiz. Endi yana ikkita g'oyaga qisqacha qaraymiz, ularni keyingi haftalarda chuqurroq o'rganamiz.

Bo'lib tashla va yengib ol

Eng tez saralashlar (masalan, birlashtirib saralash, merge sort) boshqacha ishlaydi: massivni teng ikkiga bo'ladi, har yarmini alohida saralaydi, so'ng ikki saralangan yarmni birlashtiradi. Bu yondashuv O(n log n) tezlik beradi, O(n^2) dan ancha yaxshi. Uni "bo'lib tashla va yengib ol" (divide and conquer) deyishadi.

Rekursiya

Yuqoridagi "har yarmini alohida sarala" qadami qiziq: funksiya o'z-o'zini, kichikroq qism ustida chaqiradi. Bu rekursiya deyiladi, funksiyaning o'zini chaqirishi. Bu kuchli, lekin nozik tushunchani 8-haftada to'liq o'rganamiz.

Atamalar lug'ati

5.11 Bilim testi

16 ta savol. Haftani yakunlash uchun kamida 11 tasiga to'g'ri javob bering.