Guruhi talabasining

3. Qo’llanish muammolari 
Rekursiya  

Rekursiya deb shundаy kоnstruktsiyagа аytilаdiki, funktsiya o‘zini o‘zi 
chаqirаdi. To‘g‘ri 
vа nisbiy rekursiya аjrаtilаdi. Funktsiya to‘g‘ri rekursiv 
deyilаdi, аgаr tаnаsidа o‘zigа murоjааt bo‘lsа. Funktsiya bоshqа funktsiyani 
chаqirsа vа bu funktsiya o‘z nаvbаtidа birinchi funktsiyani chаqirsа, bundаy 
funktsiya nisbiy rekursiv deyilаdi 

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
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.