Ajrat va hukmronlik qil

Ajrat va hukmronlik qil paradigmasi asosiy masalalari:

• 
  Bu paradigma dasturlashning juda mashhur algoritmlari asosini tashkil qiladi:
  

• 
  Ikkilik qidirish (Binary Search)
  

• 
  Merge Sort
  

• 
  Quick Sort
  

• 
  Eng yaqin ikki nuqta (Closest two points)
  

• 
  Strassen ko’paytirishi (Strassen multiplication)
  

• 
  Karatsuba algoritmi (Karatsuba algorithm)
  

• 
  Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
  

Quiksort – tez saralash algoritmi “ajrat va hukmronlik qil” tamoyilining yaqqol misolidir. Bu algotirm rekursiv bo’lib, o’rtacha N*log2N ta solishtirish natijasida saralaydi. Algoritm berilgan massivni saralash uchun uni 2 taga bo’lib oladi. Bo’lib olish uchun ixtiyoriy elementni tanlab undan 2 ta qismga ajratiladi.
Lekin o’rtadagi elementni tanlab, massivning teng yarmidan 2 ga ajratgan ma’qul. Tanlangan kalit elementga nisbatan chapdagi va o’ngdagi har bir element solishtiriladi. Kalit elementdan kichiklar chapga, kattalar o„ng tomonga o’tkaziladi. Endi massivning har ikkala tomonida xuddi yuqoridagi amallar takrorlanadi. Ya’ni bu oraliqlarning o’rtasidagi elementlar kalit sifatida olinadi va h.k.
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.

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.

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.