Guruhi talabasining

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
"Ajrat 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 ajrat 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. Ajrat 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.