Mustaqil ish

Stek

Stekning implementasiyasi ikki xil usulda bajarilishi mumkin. Zanjir(Linked) va Massiv.

Zanjir yoki Linked Stek.  Stekdagi barcha element o’zidan keyingi elementga bo’glangan bo’ladi va ushbu ketma-ketlik yordamida stekdagi “top” elementni aniqlab olamiz. Ushbu usulda yaratilga Stekning vaqt murakkabligi quyidagi jadvalda berilgan.

Amal	Murakkablik
Push(T value)	\(O(1)\)
Pop()	\(O(1)\)
Peek()	\(O(1)\)
IsEmpty()	\(O(1)\)
Size()	\(O(1)\)

Barcha amallarni asosini o’zlashtirish amali tashkil qilgani sababi barcha metodlar \(O(1)\) vaqtda bajariladi.

Massivga asoslangan Stek. Massivning qulayliklaridan biri bu indeks orqali massivda joylashgan elementni vaqtda qaytara olishdir. Lekin massivdagi elementlar soni ko’payib ketsa qimmatbaho amal – hajmni kengaytirish lozim bo’ladi. O’z hajmini o’zi o’zgartira oladigan massiv dinamik massiv deyiladi.

Amal	Murakkablik
Push(T value)	Resize()ga qarang.
Pop()	\(O(1)\)
Peek()	\(O(1)\)
IsEmpty()	\(O(1)\)
Size()	\(O(1)\)
Resize()	Eng yomon holatda \(O(n)\), o’rtacha esa \(O(1)\) vaqt oladi.

Nazariyaga ko’ra Push(T value) O(n) bu eng yomon holatdur, lekin Resize()ning chaqirilish ehtimolligi har chaqirilgandan so’ng pasayib boradi. Natijada, yuqoridagi metodni vaqt murakkablikka ega deb qabul qilishimiz mumkin.

4. Misollar

Merge Sort algoritmi va uning ishlash prinsipi

"Bo'lib tashla va hukmronlik qil" usulining eng mashhur saralash algoritmlaridan biri Merge Sort (Birlashtirib saralash)dir. Merge Sort algoritmi bu saralanmagan massivni taqqoslashga asoslangan holda saralovchi algoritm bo'lib, uning ishlash printsipida to'liq bo'lib tashla va hukmronlik qil g'oyasini uchratish mumkin.

Demak, merge sort algoritmi asosiy ikkita qismdan iborat:

• 
  Berilgan massivni rekursiv holda teng ikkita qismlarga bo'lib chiqish. Bu qadam, qism massivlar uzunligi 1 ga (yoki undan kichik) teng bo'lib qolguncha davom etadi.
  
• 
  Hosil bo'lgan massivlarni qaytib birlashtirib chiqish va bir vaqtning o'zida hosil bo'luvchi massiv saralangan bo'lishini ta'minlash.
  

Merge sort algoritmi qanday ishlashini vizual tasavvur qilish uchun quyidagi rasmga e'tibor bering. Unda amallar tartibi ham ko'rsatib qo'yilgan(6.3-rasm).

6.3-rasm. Merge sort algoritmining ishlash printsipi.

Ko'rib turganingizdek algoritm ishlash prinsipini tushunish uchun unchalik ham murakkab emas. Va yana e'tibor bergan bo'lsangiz, birinchi bo'linishdan keyingi massivning chap va o'ng qismlarida asosiy massiv bilan bir xil amal ketmoqda, ya'ni bizning masalamizning qism masalasi ham bosh masala bilan bir xilda ishlaydi.

Merge sort algoritmi qadamlari:

1. Merge Sort funksiyasiga massiv va uning boshlang'ich (left) va oxirgi nuqtalari (right) beriladi.

2. Massivning o'rtasi hisoblanadi: mid = (left + right)/2. Bu uni teng ikkiga bo'lish uchun kerak bo'ladi.

3. Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.

4. 2- va 3-qismlarda hosil bo'lgan massivlar birlashtirib chiqiladi. (Massiv mavzusidagi ikkita massivni birlashtirish masalasini ko'rib chiqing)

Algoritm ishlash tezligi O(nlogn) bo'lib tezligi O(n²) bo'lgan oddiy Bubble, Insertion, Selection Sortlardan ancha tez ishlaydi. O'zi umuman olganda, taqqoslash asosida ishlaydigan algortmlarning eng tez ishlash holati O(nlogn) bo'lishi isbotlangan. Merge sort turg'un saralash hisoblanadi, ya'ni saralamagan massivda bir nechta bir xil elementlar kelgan bo'lsa, ularning tartibi saralangan massivda ham o'zgarib ketib qolmaydi. Algoritm ishlashi uchun xotiradan qo'shimcha O(n) joy talab qiladi. Bo'lib tashla va hukmronlik qil paradigmasi asosida ishlaydigan eng mashhur algoritm — bu ikkilik qidirish (binary search). Ikkilik qidirish algoritmi saralangan massivdan element topishning eng samarali algoritmlaridan biri.

Chiziqli qidirish algoritmi

Chiziqli qidirish algoritmi juda oddiy algoritm bo'lib, u massivdagi har bir elementni qidirilayotgan element bilan birma-bir solishtirib chiqadi. Algoritm murakkabligi O(n) bo'lib, bu real hayotda juda ham sekin bo'lishi mumkin. Tasavvur qilaylik Facebookning 1 mlrd foydalanuvchisi bor va foydalanuvchi o'z profiliga kirmoqchi. Bunda Facebook foydalanuvchi loginini chiziqli qidirishdan foydalanib tekshiradigan bo'lsa va bunda kompyuter sekundiga 10⁶ ta loginni tekshirgan taqdirda ham, o'sha foydalanuvchi profiliga kirishi uchun 1000 soniya (16.6 daqiqa) kutishi kerak bo'lardi. Shu sababli ham bunday holatlar uchun bizga samaraliroq algoritmlar kerak bo'ladi.



Ikkilik qidirish algoritmining ishlash prinsipi

Ikkilik qidirish algoritmini ishlash prinsipini tushunish uchun keling kompyuter bilan o'yin o'ynab ko'ramiz. O'yin shartlari quyidagicha:

1. Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu sonni iloji boricha kam taxmin ishlatgan holda topish.

2. Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter o'ylagan sondan katta yoki kichikligini aytadi.

3. Agar sizning taxminingiz kompyuter o'ylagan son bilan bir xil bo'lsa, o'yin tugaydi.

Xo'sh, bunda kamroq yo'l tutish uchun nima qilgan bo'lar edingiz?

Albatta, birinchi navbatda o'rtadagi sonni taxmin qilib ko'ramiz, ya'ni 50 ni(6.4-rasm):

6.4-rasm. Ikkilik qidirish algoritmining ishlash prinsipi.

Aytaylik kompyuter bizga taxminimiz o'ylangan sondan kichikroq ekanligini aytdi. Demak, endi biz 50 va undan kichik barcha son o'ylangan sondan kichik ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar o'rtasidagi sonni olamiz, ya'ni 75 ni(6.5-rasm).

6.5-rasm. Ikkilik qidirish algoritmining ikkinchi qadami.

Kompyuter bizga 75 o'ylangan sondan katta ekanligini aytdi. Demak, 75 dan katta barcha sonlar ham o'ylangan sondan katta ekan. Shunday qilib, bizdagi qidirish sohasi yana ikki baravarga qisqardi (25 ta son). Huddi shunday davom etib, biz o'ylangan sonni topishimiz mumkin(6.6-rasm).

6.6-rasm. Ikkilik qidirish algoritmining keyingi qadamlari.

Sonlar 100 ta bo'lgan holatda, biz har qanday tahminni ko'pi bilan 7 ta qadamda topishimiz mumkin bo'ladi. Ikkilik qidirish algoritmi ham huddi shunday prinsipda ishlaydi!

Algoritm qadamlari

Ikkilik qidirish algoritmi to'g'ri ishlashi uchun massiv saralangan bo'lishi shart! Bizda n ta elementli saralangan massiv bor va biz undan x elementni qidirmoqdamiz. Biz qidirish chegarasini belgilash uchun l (left) va r (right) ko'rsatkichlardan foydalanamiz. Ular massiv indekslarini ko'rsatib turadi. mid o'zgaruvchi bizda qidirilayotgan sohaning o'rtadagi elementi indeksini ko'rsatadi

1. Avvaliga l = 0 va r=n-1 bo'ladi (butun boshli massiv)

2. O'rtadagi element indeksi hisoblanadi: mid = (l + r)/2;

3. O'rtadagi element indeksi bilan qidirilayotgan son x solishtirib ko'riladi

4. Agar son mos kelsa, algoritm shu joyida to'xtaydi.

5. Agar x o'rtadagi sondan katta bo'lsa, left ko'rsatkichni o'rtadan bitta keyingi elementga suramiz: l=mid + 1;

6. Agar x o'rtadagi sondan kichik bo'lsa, right ko'rsatkichni o'rtadan bitta oldingi elementga suramiz: r=mid — 1;

7. 2-qadamga qaytiladi.

Ikkilik qidirish algoritmi har bir qadamda n ni ikki baravarga kamaytirgani uchun algoritm ishlash tezligi O(logn) hisoblanadi. Solishtirish uchun Facebook misolidagi 1 mlrd login ichidan ikkilik qidirish algoritmi 30 ta (!) qadam bilan topishi mumkin. Oddiy qidirishdan tashqari bu algoritmni yana boshqa juda ko'p joyda qo'llash mumkin.

Nazorat savollari

1. “Bo’lib tashla va hukmronlik qil” algoritmining bosqichlarini ayting.

2. Qanday saralash algoritmlarini bilasiz?

3. Saralash algoritmlari samaradorligini qanday baholash mumkin?

4. Stek tuzilmasini tushuntiring va misol keltiring.

5. Binar daraxtiga yangi element qo‟shish algoritmini tushuntiring.

6. Quicksort algoritmini tushuntiring.